Alex_ST, единственное, что я бы поправил, это условие фильтрации на более мягкое: [vba]
Код
bSimilar = TextSimilarity(sTmpl, sText) >= fSim
[/vba] А то странно, когда при 100% ничего в принципе не находится.
Цитата (Alex_ST)
я не хочу использовать FindBestMatchTxt потому, что она возвращает только одно значение, которое ПО ЕЁ МНЕНИЮ мне больше всего подходит. А я хочу доверить функции нечёткого поиска только приблизительную предварительную фильтрацию записей чтобы из результатов иметь возможность уже САМОМУ ВЫБРАТЬ наиболее подходящий мне вариант.
Меня это тоже, признаться, смущает. Надо всё-таки будет взять себя в руки и как-то организовать возврат массива.
Alex_ST, единственное, что я бы поправил, это условие фильтрации на более мягкое: [vba]
Код
bSimilar = TextSimilarity(sTmpl, sText) >= fSim
[/vba] А то странно, когда при 100% ничего в принципе не находится.
Цитата (Alex_ST)
я не хочу использовать FindBestMatchTxt потому, что она возвращает только одно значение, которое ПО ЕЁ МНЕНИЮ мне больше всего подходит. А я хочу доверить функции нечёткого поиска только приблизительную предварительную фильтрацию записей чтобы из результатов иметь возможность уже САМОМУ ВЫБРАТЬ наиболее подходящий мне вариант.
Меня это тоже, признаться, смущает. Надо всё-таки будет взять себя в руки и как-то организовать возврат массива.Формуляр
Excel 2003 EN, 2013 EN
Сообщение отредактировал Формуляр - Вторник, 30.08.2011, 18:11
Ждём-с с нетерпением! А никаких наработок по нечёткому поиску шаблона из нескольких (до 5-8 максимум, наверное) слов в массиве длинных стрингов нет? Это, например, очень нужно при поиске по адресу, т.к. адреса при ручном вводе пишут кто как хочет, особенно если название состоит из нескольких слов (ул. Зои и Александра Космодемьянских, Космонавта Волкова улица и т.д. и т.п.). А уж если там есть числительные (2-я Шарикоподшипниковская ул., Новоподмосковная 5-я ул., 444-й проектируемый проезд … ) то вообще хана!
Ждём-с с нетерпением! А никаких наработок по нечёткому поиску шаблона из нескольких (до 5-8 максимум, наверное) слов в массиве длинных стрингов нет? Это, например, очень нужно при поиске по адресу, т.к. адреса при ручном вводе пишут кто как хочет, особенно если название состоит из нескольких слов (ул. Зои и Александра Космодемьянских, Космонавта Волкова улица и т.д. и т.п.). А уж если там есть числительные (2-я Шарикоподшипниковская ул., Новоподмосковная 5-я ул., 444-й проектируемый проезд … ) то вообще хана!Alex_ST
Формуляр, а почему FindBestMatchTxt должен работать быстрее чем TextSimilarity? Разве в чём-то есть их принципиальное отличие? (алгоритмы, повторяюсь, я анализировать не стал, т.к. нет их описания, а только рабочие комментарии в кодах)
Формуляр, а почему FindBestMatchTxt должен работать быстрее чем TextSimilarity? Разве в чём-то есть их принципиальное отличие? (алгоритмы, повторяюсь, я анализировать не стал, т.к. нет их описания, а только рабочие комментарии в кодах)Alex_ST
Привинтил сравнение по дереву двоичной сортировки. И мониторинг числа несовпадающих символов на превышение предела, выше которого текущий максимум теоретически уже недостижим.
Наверное, сформулировал не очень понятно, но без обращения к кодам объяснить трудновато. 1ое - вполне заезженный способ оптимизации поиска и сравнения. Макс. необходимое число циклов - Log2(Len), при линейном поиске - просто Len. Насколько он быстрее, чем InStr() - вопрос открытый. 2ое - прерывает цикл сравнения диад, как только несовпадающих становится больше, чем теоретически допустимо для превышения сходства, лучшего из уже найденных.
Alex_ST,
Quote (Формуляр)
Привинтил сравнение по дереву двоичной сортировки. И мониторинг числа несовпадающих символов на превышение предела, выше которого текущий максимум теоретически уже недостижим.
Наверное, сформулировал не очень понятно, но без обращения к кодам объяснить трудновато. 1ое - вполне заезженный способ оптимизации поиска и сравнения. Макс. необходимое число циклов - Log2(Len), при линейном поиске - просто Len. Насколько он быстрее, чем InStr() - вопрос открытый. 2ое - прерывает цикл сравнения диад, как только несовпадающих становится больше, чем теоретически допустимо для превышения сходства, лучшего из уже найденных.Формуляр
Excel 2003 EN, 2013 EN
Сообщение отредактировал Формуляр - Среда, 31.08.2011, 10:55
Ну вот, как мог привинтил на лист FuzzyFILTER. Для оценки производительности надо бы массив помассивнее подгрузить (записей на 1000). Сильно быстро бегает однако.
Ну вот, как мог привинтил на лист FuzzyFILTER. Для оценки производительности надо бы массив помассивнее подгрузить (записей на 1000). Сильно быстро бегает однако. Формуляр
Что-то у меня ближе к вечеру башка не варит... Завтра покручу. Надо будет первым делом для ясности лишние процедуры модули убрать, а потом уж разбираться. К стати, вы не думаете, что из поиска похожести имеет смысл исключить слова менее чем из 3-х букв? Наверное, побыстрее будет? И что-то я не увидел (или не нашёл) очистки шаблона и фильтруемых фраз от шелухи (лишние пробелы и все знаки препинания)? Или вы считаете, что этого делать не надо?
Что-то у меня ближе к вечеру башка не варит... Завтра покручу. Надо будет первым делом для ясности лишние процедуры модули убрать, а потом уж разбираться. К стати, вы не думаете, что из поиска похожести имеет смысл исключить слова менее чем из 3-х букв? Наверное, побыстрее будет? И что-то я не увидел (или не нашёл) очистки шаблона и фильтруемых фраз от шелухи (лишние пробелы и все знаки препинания)? Или вы считаете, что этого делать не надо?Alex_ST
С уважением, Алексей MS Excel 2003 - the best!!!
Сообщение отредактировал Alex_ST - Четверг, 01.09.2011, 16:24
И что-то я не увидел (или не нашёл) очистки шаблона и фильтруемых фраз от шелухи (лишние пробелы и все знаки препинания)? Или вы считаете, что этого делать не надо?
Очистку я убрал, так как при сравнении игнорируются все знаки, кроме букв. Это, кстати, может быть в каких-то случаях минусом.
Quote (Alex_ST)
К стати, вы не думаете, что из поиска похожести имеет смысл исключить слова менее чем из 3-х букв? Наверное, побыстрее будет?
Поскольку сравнение происходит парами знаков (диадами), "вес" слова оказывается примерно пропорционален его длине. А совсем исключать - это целый огород городить. Да и жалко их...
Quote (Alex_ST)
И что-то я не увидел (или не нашёл) очистки шаблона и фильтруемых фраз от шелухи (лишние пробелы и все знаки препинания)? Или вы считаете, что этого делать не надо?
Очистку я убрал, так как при сравнении игнорируются все знаки, кроме букв. Это, кстати, может быть в каких-то случаях минусом.
Quote (Alex_ST)
К стати, вы не думаете, что из поиска похожести имеет смысл исключить слова менее чем из 3-х букв? Наверное, побыстрее будет?
Поскольку сравнение происходит парами знаков (диадами), "вес" слова оказывается примерно пропорционален его длине. А совсем исключать - это целый огород городить. Да и жалко их... Формуляр
А нельзя на диадами, а триадами (в хорошем смысле слова) сравнивать? Или сначала просто отбросить все слова, которые короче 3-х букв, а потом уже искать?
А нельзя на диадами, а триадами (в хорошем смысле слова) сравнивать? Или сначала просто отбросить все слова, которые короче 3-х букв, а потом уже искать?Alex_ST
Можно. Но кое-что придётся переделать, в частности - тот самый кусок, который пропускает небуквенные символы. Только надо осознавать, что в результате "Мыть" и "НЕ мыть" дадут 100% схдства. Для моей задачи, например, это не желательно. Было поползновение сделать длину фрагмента настраиваемой (ввёл константу Q), но полезли мелкие баги и дело застопорилось...
Можно. Но кое-что придётся переделать, в частности - тот самый кусок, который пропускает небуквенные символы. Только надо осознавать, что в результате "Мыть" и "НЕ мыть" дадут 100% схдства. Для моей задачи, например, это не желательно. Было поползновение сделать длину фрагмента настраиваемой (ввёл константу Q), но полезли мелкие баги и дело застопорилось...Формуляр
"По просьбам трудящихся" добавил сравнение триадами. Q-фактор (длина фрагмента сравнения) теперь настраивается через Const Q. Написал UDF, возвращающую рейтинг строк по сходству с образцом. И ещё немножко дожал производительность.
"По просьбам трудящихся" добавил сравнение триадами. Q-фактор (длина фрагмента сравнения) теперь настраивается через Const Q. Написал UDF, возвращающую рейтинг строк по сходству с образцом. И ещё немножко дожал производительность.Формуляр
Формуляр, не обижайтесь, но, хоть диадами, хоть триадами, а всё равно, не зная теории, на основании которой построен алгоритм и имея при этом комментарии типа
Quote
'в 1ом цикле добавляем нов. диаду к дереву 'кроме корня 'В повторных циклах новые диады просто считаем в 0-ом поле профиля '--- в 1ом цикле считаем "площадь" искомого профиля 'Выравнивание двоичного дерева по глубине
разобраться в том, почему при введённом шаблоне (Template) "помогите" значению "Формулы для столовой" (B3) с точностью 42,9% находится соответствующее "Помогите пожалуйста", ну никак не могу...
Формуляр, не обижайтесь, но, хоть диадами, хоть триадами, а всё равно, не зная теории, на основании которой построен алгоритм и имея при этом комментарии типа
Quote
'в 1ом цикле добавляем нов. диаду к дереву 'кроме корня 'В повторных циклах новые диады просто считаем в 0-ом поле профиля '--- в 1ом цикле считаем "площадь" искомого профиля 'Выравнивание двоичного дерева по глубине
разобраться в том, почему при введённом шаблоне (Template) "помогите" значению "Формулы для столовой" (B3) с точностью 42,9% находится соответствующее "Помогите пожалуйста", ну никак не могу...Alex_ST
разобраться в том, почему при введённом шаблоне (Template) "помогите" значению "Формулы для столовой" (B3) с точностью 42,9% находится соответствующее "Помогите пожалуйста", ну никак не могу...
Alex_ST, это % сходства с Template, а не с соседним столбцом. Извините - поленился добавить лишний пустой ст-ц.
Что касается комментариев и теории, то вы совершенно правы. Я, собственно, и не претендовал на прозрачность кода. Наоборот - комментарии, скорее, пришлось писать для себя, поскольку в процессе оптимизации алгоритмы сильно отклонились от прямой реализации заложенной теории.
Общий принцип таков: для 2-х строк формируем общий набор трид или диад (в общем Q-грамм, как пишут умные люди). Для каждой строки строится частотный профиль встречаемости каждой диады (как правило, 1 либо 0). Сумма этих значений и есть "площадь" профиля, т.е. просто кол-во полных диад в данной строке. А дальше, "площадь" пересекающейся части 2-х профилей делится на общую "площадь" их объединения. Это и есть наша метрика.
Описывать подробно, как это реализовано, займёт кучу времени. Лучше задавайте вопросы по отдельным кускам, в которых хотите разобраться или что-то модифицировать.
Quote (Alex_ST)
разобраться в том, почему при введённом шаблоне (Template) "помогите" значению "Формулы для столовой" (B3) с точностью 42,9% находится соответствующее "Помогите пожалуйста", ну никак не могу...
Alex_ST, это % сходства с Template, а не с соседним столбцом. Извините - поленился добавить лишний пустой ст-ц.
Что касается комментариев и теории, то вы совершенно правы. Я, собственно, и не претендовал на прозрачность кода. Наоборот - комментарии, скорее, пришлось писать для себя, поскольку в процессе оптимизации алгоритмы сильно отклонились от прямой реализации заложенной теории.
Общий принцип таков: для 2-х строк формируем общий набор трид или диад (в общем Q-грамм, как пишут умные люди). Для каждой строки строится частотный профиль встречаемости каждой диады (как правило, 1 либо 0). Сумма этих значений и есть "площадь" профиля, т.е. просто кол-во полных диад в данной строке. А дальше, "площадь" пересекающейся части 2-х профилей делится на общую "площадь" их объединения. Это и есть наша метрика.
Описывать подробно, как это реализовано, займёт кучу времени. Лучше задавайте вопросы по отдельным кускам, в которых хотите разобраться или что-то модифицировать.Формуляр
Excel 2003 EN, 2013 EN
Сообщение отредактировал Формуляр - Понедельник, 19.09.2011, 15:38
Дата: Понедельник, 19.09.2011, 17:32 |
Сообщение № 38
Группа: Гости
>>Кстати, вы не думаете, что из поиска похожести имеет смысл исключить слова менее чем из 3-х букв? Наверное, побыстрее будет?
До того, как заняться функцией нечеткого поиска (в моем случае, поиска с допуском одной ошибки ввода), ляпил функцию "анти-плагиат", т.е. сравнение похожих текстов. Постараюсь перечислить основные моменты, кот. считаю важными в этом деле:
1. Очистка сравниваемых текстов/строк от всех символов кроме цифр и букв [vba]
Код
Private Function CleanString(ByVal Str$) As String Dim i%, x As String * 1 Do While i < Len(Str) i = i + 1: x = Mid(Str, i, 1) If Not x Like "[0-9A-Za-zА-яЁё ]" Then Str = Replace(Str, x, ""): i = i - 1 End If Loop CleanString = Replace(Trim(Str), " ", " ") End Function
[/vba]
Почему именно эта (под эта понимать смысл её действия) функция, а не .Pattern = "[\_,\-,\/,\.,\,\!,\@,\#,\$,\%,\^,\&,\*,\(,\),\+,\=,\{,\},\[,\],\|,\\,\;,\:,\',\"",\<,\?,\`,\~]" ? Есть т.н. невидимые символы, символы вставленные, к примеру, из Word'а. Тот же длинный дефис. Пример невидимого символа http://www.planetaexcel.ru/forum.php/?thread_id=11364
2. Наверное все-таки при сравнении больших объемов текста, приведение к единому регистру. Допустим слово может употребляться в начале предложения, может в его середине, конце. 3. Исключить из сравнения, т.к. стоп-слова, или слова паразиты и/или не несущие смысловую нагрузку: вот, вас, его, мои, ниx, так, или, что. Список очень длинный у меня на данный момент набралось чуть-более 600. И еще я считаю, что имеет смысл все что меньше 2 символов исключить из обработки (хотя цифры можно оставить, наверное). 4. Проверить орфографию если это возможно. 5. Привести к ед. числу, одному падежу т.п. (впрочем, это очень накладно). 6. Отсортировать сравниваемые тексты/строки.
Пока остановился на этом, ибо меня интересовало сравнение текстов. Там немного иначе все обстоит. Как мне кажется, слишком накладно сравнивать тексты алгоритмами, приведенными выше. Хотя я в них не разбирался, мельком глянул.
p.s.: не зарег. пользователю можно файлы прикреплять? Не разберусь ни как в форуме
>>Кстати, вы не думаете, что из поиска похожести имеет смысл исключить слова менее чем из 3-х букв? Наверное, побыстрее будет?
До того, как заняться функцией нечеткого поиска (в моем случае, поиска с допуском одной ошибки ввода), ляпил функцию "анти-плагиат", т.е. сравнение похожих текстов. Постараюсь перечислить основные моменты, кот. считаю важными в этом деле:
1. Очистка сравниваемых текстов/строк от всех символов кроме цифр и букв [vba]
Код
Private Function CleanString(ByVal Str$) As String Dim i%, x As String * 1 Do While i < Len(Str) i = i + 1: x = Mid(Str, i, 1) If Not x Like "[0-9A-Za-zА-яЁё ]" Then Str = Replace(Str, x, ""): i = i - 1 End If Loop CleanString = Replace(Trim(Str), " ", " ") End Function
[/vba]
Почему именно эта (под эта понимать смысл её действия) функция, а не .Pattern = "[\_,\-,\/,\.,\,\!,\@,\#,\$,\%,\^,\&,\*,\(,\),\+,\=,\{,\},\[,\],\|,\\,\;,\:,\',\"",\<,\?,\`,\~]" ? Есть т.н. невидимые символы, символы вставленные, к примеру, из Word'а. Тот же длинный дефис. Пример невидимого символа http://www.planetaexcel.ru/forum.php/?thread_id=11364
2. Наверное все-таки при сравнении больших объемов текста, приведение к единому регистру. Допустим слово может употребляться в начале предложения, может в его середине, конце. 3. Исключить из сравнения, т.к. стоп-слова, или слова паразиты и/или не несущие смысловую нагрузку: вот, вас, его, мои, ниx, так, или, что. Список очень длинный у меня на данный момент набралось чуть-более 600. И еще я считаю, что имеет смысл все что меньше 2 символов исключить из обработки (хотя цифры можно оставить, наверное). 4. Проверить орфографию если это возможно. 5. Привести к ед. числу, одному падежу т.п. (впрочем, это очень накладно). 6. Отсортировать сравниваемые тексты/строки.
Пока остановился на этом, ибо меня интересовало сравнение текстов. Там немного иначе все обстоит. Как мне кажется, слишком накладно сравнивать тексты алгоритмами, приведенными выше. Хотя я в них не разбирался, мельком глянул.
p.s.: не зарег. пользователю можно файлы прикреплять? Не разберусь ни как в форуме Гость
Вход
Регистрация
Напомнить пароль
Автосумма
Часто используемые
ВПР
ЕСЛИ
СУММЕСЛИ
Финансовые
Логические
Текстовые
Даты и времени 
Ссылки и массивы 
Математические
Другие функции
Проверка свойств и значений
Баз данных
Математические
Обработки массивов
Обработки строк
Преобразования типов данных 
Загрузки данных
Работы с файлами
Обработки системных параметров
Обработки цвета
Работы с датами и временем
Преобразования в системы счисления
Финансовые
… ) то вообще хана!
