Добрый день!
Подскажите, пожалуйста, алгоритм сравнения строк (текста) на похожесть.
Оговорюсь сразу, прочитал достаточно статей с того же Хабра на эту тему, много там математики и очень уж сложно все. Да и ресурсозатратно тоже.
И напротив - такие методы как similar_text() или levenshtein() тоже не очень подходят, ибо показывают плохой результат в случае простой перестановки слов в строке.
Хотелось бы найти готовый алгоритм, а еще лучше уже написанный метод на php, js или каком другом языке, который будет и не очень сложен и затратен, но и в то же время достаточно точен в оценке.
P.S. В этой сфере не специализируюсь, поэтому навскидку сразу не могу найти нужный материал.
И напротив - такие методы как similar_text() или levenshtein() тоже не очень подходят, ибо показывают плохой результат в случае простой перестановки слов в строке.
Можно попробовать использовать алгоритм не на уровне букв, а на уровне слов (токенов). При этом уменьшить (или обнулить) вес обмена слов
будет и не очень сложен и затратен, но и в то же время достаточно точен в оценке
Разговорный русский или английский?
Скажу проще - в русском языке исключений столько, что с одним лингвистом не разберёшь.
Но помечтать никто не запрещает :3
sim3x, ну не надо так прям буквально. Проще надо быть :)
Просто есть люди, которые такой же темой занимались ранее, вот они то и знают хорошо подводные камни различных реализаций алгоритмов, включая всем известный Левенштейна.
И хотелось бы услышать мнение этих людей, а не теоретиков от Гугла, умеющих только в ссылки тыкать...
Дѣаволъ, ну всем же известно, что только из мечты рождается что-то действительно стоящее :) Банальщины и серости и так хватает...
По сабжу - ну по любому кто-то реализовывал промежуточные варианты с уклоном в ту или иную сторону(сложности или точности), так что может повезет и найду такую реализацию.
sim3x, будьте добры - несколько практических примеров готовой реализации, чтобы более предметно разговаривать. А то может быть я действительно ошибаюсь, и совсем не то имею ввиду.
Если б я сам до конца понимал эти критерии..
Пока в стадии формирования.
Результат видится как то так: текст похож на 87%
А уж как он будет считаться - по количеству букв, слов, лексем, токенов, шинглов, и бог его знает еще чего - не знаю.
Поэтому и ищу информацию которая подскажет как лучше что использовать.
С таким образом поставленной задачей не получится работать, увы )
Рифмы — тоже похожие строки. Так что порог и критерии «похожести» это половина решения, останется только подобрать метод из уже готовых: нечеткий поиск для опечаток как предлагали выше, LSI или word2vec для смысловой/тематической похожести, фонетическая и т.д. Может вам вообще подойдет простая эвристика.
Андрей Федосеев, я это понимаю, что критерии - главная часть задачи.
Но т.к. не специалист, сложно с чего то начать.
Спасибо за наводку вариантов :) будем гуглить
Stalker_RED, не нужно гадать. Просто предложите свой вариант, опыт работы с которым у вас есть. Представьте, что я - нейросеть. И вы мне накидываете варианты для обучения сети (т.е. меня). Я просмотрю предложенные варианты и определю по ним критерии дальнейшего поиска. И уже тогда смогу задать правильные вопросы. Собственно, для этого и создаются такие ресурсы как Тостер etc. И таки да, поясню для Гуглоссылателей - если не знаешь, что конкретно искать, там можно перелопатить тонны материала, и - ничего не найти!
P.S. Отдельное спасибо всем, кто не поленился и кинул ссылки на материалы или дал конкретные советы.
Но в этой области нет ничего простого, так чтобы в три строчки кода уложиться. Если конкретизировать свои хотелки вы не собираетесь, то и краткого пересказа содержимого википедии тоже не будет.
Stalker_RED, ну перестаньте же...
Если у вас машина стала плохо ехать, вы же не начинаете учить молекулярную химию топлива или внутреннее устройство программ электронных блоков управления? Вы просто меняете заправку или целиком блок.
Вот и мне не нужно в самые дебри лезть - я думаю есть много уже готовых подобных реализаций. И тот, кто занимался тем же самым - имел те же вопросы что и у меня.
Валерий В., есть некоторое количество алгоритмов сравнения текстов, их по пальцам можно пересчитать. Есть огромное количество модификаций этих алгоритмов, типа "тонкая настройка", всякие хитрые веса и параметры.
Вы взяли две стандартные библиотечные функции, немножко потестировали и сказали что они работают "не правильно". Ну ок.
И тот, кто занимался тем же самым - имел те же вопросы что и у меня.
Ну как-бы да, имел похожие вопросы. Оторвал жопу от стула, побщался с теми кто ставил задачу, узнал чего именно они хотят, какие метрики для них важны, а какие не очень. потом под эти требования искал решение.
А фигачить наугад без включения башки - желаю удачи, но без меня.
Stalker_RED, это у вас профессиональное - выдавать ваше личное представление за действительное?
Я же о другом говорю совсем. Или вы просто не хотите слышать.
Задачу я ставлю сам себе. И я не знаю как правильно сформулировать критерии. Чтобы правильно поставить задачу. Ибо не специалист. И именно поэтому я пришел сюда, чтобы задать свои вопросы тут. А вы мне в ответ - какой я умный, все знаю, но вам не скажу ничего и не помогу ничем, потому что вы не знаете что нужно. Это я про вас. А другие здесь писавшие тоже не знают что мне нужно, но пытаются дать мне хоть какую-то информацию. И спасибо им за это, я хоть начинаю понимать, какую информацию мне надо искать.
Поэтому вам алаверды - последняя ваша фраза. Но в отношении к вам уже.
Валерий В., Вот так из двух строчек текста мы тут понаписали уже на два экрана какой-то воды.
кстати, я думаю, для начала мне хватит и similar_text() или levenshtein(), но как заставить их правильно работать с перестановкой слов?
Вы можете вот это объяснить? Я верю что вы не можете правильно сформулировать критерии, но хоть немного вы можете пролить свет на то, какое поведение вы ожидаете?
Вы можете вот это объяснить?
Вот это вы можете объяснить?
Вот этовы можете объяснить?
Вот это вы может объяснить?
Вот это можете объяснить?
Это можете объяснить?
Это можете объяснить
Валерий В., лол )
убираете знаки препинания, приводите слова к одному регистру, сортируете слова в фразе по алфавиту, убираете предлоги или просто 3х-буквенные. Или не убираете, а приписываете им коэфициент за "вклад в похожесть". Берете шинглы Х длины, где X 1/2 от количества слов в фразе. Или 1/3, 1/5, подбираете вес «похожести» в общем.
Пример за минуту придумал, но тут копать можно много.
Вариант для ограниченного словаря слов.
-Составляем массив всех слов из текстов, поиск по которым будем вести. Каждое слово обрабатываем стеммером. Выкидываем короткие основы. Оставляем в массиве только уникальные основы.
-Каждую строку по которой будем искать превращаем в массив, состоящий из индексов основ слов в словаре. Сортируем массив.
-Аналогично делаем со строкой которую будем искать. Так как в ней могут быть новые слова, чтобы найти индекс основы слова в словаре, ищем основу с наименьшим левенштейном по отношению к данной основе слова. Сортируем массив.
-Теперь похожесть текстов можем сравнивать, как длинну разности массивов индексов.
Ну скажем так - при желании я сам смогу это организовать.
Я же поэтому и ищу - "простой" - вариант, чтобы не так точно как в профессиональном подходе, но в то же время и без особых затрат (материальных и других) реализовать простую обработку сравнения.
Валерий В., Куда уж проще, чем я описал. В сотню строк легко можно уложиться, если речь о js или php. Я привел алгоритм, который реально использовал в одном из проектов на с++ (там конечно побольше кода это заняло + порядок слов все-таки учитывался, то есть не было этапа сортировки). Суть была в компенсации неточности OCR распознавания. Работает достаточно быстро.
В вашем случае последний и частично предпоследний этап можно перенести на сторону БД - будет еще быстрее. https://habrahabr.ru/post/342434/
Как на счёт расстояния Левенштейна и прочие модификации данного алгоритма? Потом накидывать уже свой алгоритм под нужды: порядок/отсутствие слов и т.д.
Таки да, может быть, и скорее всего оно. Но нужна конкретная реализация, а их очень много.
Именно поэтому нужен совет практика, не уровня гугломылояндекса, а простого среднего проекта. Есть жигули шестерка, есть ролс-ройс, а мне нужно что-то типа БМВ. Это чтобы было понятнее. Поэтому и говорю - мне бы хватило similar_text() или levenshtein(), но если бы не менялся результат от перестановки слов. И не тупо считать количество букв.
Простой
Простой