Каков наилучший алгоритм для сопоставления двух строк, содержащих менее 10 слов в латинском языке script

Я сравниваю названия песен, используя латинский script (хотя и не всегда), моя цель - это алгоритм, который дает высокий балл, если два названия песен кажутся одинаковыми, и очень низкий балл, если они не имеют ничего общего.

Теперь мне уже пришлось написать код (Java), чтобы написать это с помощью Lucene и RAMDirectory - однако использование Lucene просто для сравнения двух строк слишком тяжело и, следовательно, слишком медленно. Я перешел к использованию https://github.com/nickmancol/simmetrics, у которого есть много хороших алгоритмов для сравнения двух строк:

https://github.com/nickmancol/simmetrics/tree/master/src/main/java/uk/ac/shef/wit/simmetrics/similaritymetrics

BlockDistance
ChapmanLengthDeviation
ChapmanMatchingSoundex
ChapmanMeanLength
ChapmanOrderedNameCompoundSimilarity
CosineSimilarity
DiceSimilarity
EuclideanDistance
InterfaceStringMetric
JaccardSimilarity
Jaro
JaroWinkler
Levenshtein
MatchingCoefficient
MongeElkan
NeedlemanWunch
OverlapCoefficient
QGramsDistance
SmithWaterman
SmithWatermanGotoh
SmithWatermanGotohWindowedAffine
Soundex

но я не очень разбираюсь в этих алгоритмах и что будет хорошим выбором?

Я думаю, что Lucene использует CosineSimilarity в той или иной форме, так что это моя отправная точка, но я думаю, что может быть что-то лучше.

В частности, алгоритм должен работать на коротких строках и должен понимать концепцию слов, т.е. места должны обрабатываться специально. Хорошее совпадение латинского script является самым важным, но хорошее соответствие другим сценариям, таким как корейский и китайский, тоже актуально, но я ожидаю, что потребуется другой алгоритм из-за того, как они обрабатывают пробелы.

Ответ 1

Они все хороши. Они работают с различными свойствами строк и имеют разные подходящие свойства. Что лучше всего подходит для вас, зависит от того, что вам нужно.

Я использую JaccardSimilarity для соответствия именам. Я выбрал JaccardSimilarity, потому что он был достаточно быстрым и для коротких строк превосходил совпадающие имена с обычной опечаткой, а также быстро ухудшал оценку для чего-либо еще. Придает дополнительный вес пробелам. Это также нечувствительно к порядку слов. Мне нужно было такое поведение, потому что влияние ложного положительного было намного выше, чем от ложного отрицательного, пробелы могли быть опечатками, но не часто, а порядок слов не был таким важным.

Обратите внимание, что это было сделано в сочетании с упростителем, который удаляет недиакритические символы и карту, который отображает оставшиеся символы в диапазон a-z. Это передается через нормализующее значение, которое стандартизирует все символы разделителя слов в одном пространстве. Наконец, имена анализируются, чтобы выбирать начальные, предварительные и суффиксы. Это потому, что имена имеют структуру и формат для них, что довольно устойчиво к просто сравнению строк.

Чтобы сделать свой выбор, вам нужно составить список критериев, которые вы хотите, а затем искать алгоритм, удовлетворяющий этим критериям. Вы также можете сделать достаточно большой набор тестов и запустить все алгоритмы на этом тестовом наборе, чтобы узнать, какие компромиссы относятся к времени, количеству положительных результатов, ложным срабатываниям, ложным негативам и негативам, классам ошибок, которые должна обрабатывать ваша система, ect, ect.

Если вы по-прежнему не уверены в своем выборе, вы также можете настроить свою систему для переключения точных алгоритмов сравнения во время выполнения. Это позволяет вам выполнить тест A-B и посмотреть, какой алгоритм работает лучше всего на практике.

TL;DR; какой алгоритм вы хотите, зависит от того, что вам нужно, если вы не знаете, что вам нужно, убедитесь, что вы можете впоследствии его изменить и запустить тесты на лету.

Ответ 2

Вероятно, вам нужно решить проблему исправление строки в строку. Алгоритм расстояния Левенштейна реализован на многих языках. Перед запуском я удаляю все пробелы из строки, потому что они не содержат никакой важной информации, но могут влиять на разницу двух строк. Для строкового поиска префиксные деревья также полезны, вы также можете посмотреть в этом направлении. Например здесь или здесь. Уже обсуждался в fooobar.com/questions/146063/.... Если в вашем случае пространства настолько значительны, просто назначьте им больший вес.

Ответ 3

Каждый алгоритм будет фокусироваться на подобном, но немного другом аспекте двух строк. Честно говоря, это полностью зависит от того, чего вы пытаетесь достичь. Вы говорите, что алгоритм должен понимать слова, но должен ли он также понимать взаимодействия между этими словами? Если нет, вы можете просто разбить каждую строку в соответствии с пробелами и сравнить каждое слово в первой строке с каждым словом во втором. Если они разделяют слово, коэффициент общности двух строк должен увеличиваться.

Таким образом, вы можете создать свой собственный алгоритм, ориентированный только на то, что вы касались. Если вы хотите протестировать другой алгоритм, который кто-то еще сделал, вы можете найти примеры в Интернете и запустить свои данные, чтобы узнать, насколько точны оценочные общности с каждым.

Я думаю, http://jtmt.sourceforge.net/ будет хорошим местом для начала.

Ответ 4

Интересно. Вы думали о сортировке радикса?

http://en.wikipedia.org/wiki/Radix_sort

Концепция сортировки radix заключается в том, что она представляет собой не сравнительный целочисленный алгоритм сортировки, который сортирует данные с помощью целых ключей, группируя ключи по отдельным цифрам. Если вы преобразуете свою строку в массив символов, который будет иметь число не более 3 цифр, то ваше k = 3 (максимальное количество цифр) и вы n = количество строк для сравнения. Это отсортирует первые цифры всех ваших строк. Тогда у вас будет другой коэффициент s = длина самой длинной строки. ваш худший сценарий сортировки будет 3 * n * s, и лучшим случаем будет (3 + n) * s. Ознакомьтесь с некоторыми примерами сортировки радикса для строк здесь:

http://algs4.cs.princeton.edu/51radix/LSD.java.html

http://users.cis.fiu.edu/~weiss/dsaajava3/code/RadixSort.java

Ответ 5

Вы взглянули на расстояние Левенштейна?

int org.apache.commons.lang.StringUtils.getLevenshteinDistance(String s, String t)

Найдите расстояние Левенштейна между двумя строками.

Это число изменений, необходимых для изменения одной строки в другой, где каждое изменение является модификацией одного символа (удаление, вставка или замена).

Предыдущая реализация алгоритма расстояния Левенштейна была от http://www.merriampark.com/ld.htm

Chas Emerick написал реализацию на Java, которая позволяет избежать OutOfMemoryError, которое может возникнуть при использовании моей реализации Java с очень большими струнами. Эта реализация Левенштейна алгоритм расстояния от http://www.merriampark.com/ldjava.htm

В любом случае, мне любопытно узнать, что вы выберете в этом случае!

Ответ 6

Интересно, не пытаетесь ли вы изобретать колесо. Некоторые системы управления базами данных предлагают услуги/функции, предназначенные для такого рода задач.

например. Текст Oracle

EDIT:

Держись! Вы собираетесь сравнить названия песен, и вы НЕ используете базу данных? Это интересно. Почему вы не добавили его в свой первоначальный вопрос. Потому что более 90% промышленных приложений используют какую-то базу данных. И действительно неважно, в какой отрасли вы находитесь: производство, медицина, дистрибуция, развлечения, финансы,...

И даже если вы еще не используете базу данных, вы должны использовать ее. В эти дни есть все виды dbms. Они приходят во все вкусы: реляционные, объектно-ориентированные; двоичный или xml; встроенный или автономный; multifile или singlefile. Если честно, если вы не используете базу данных, вам тяжело это сделать.

Но , если, вы используете базу данных Oracle для хранения ваших песен. Тогда Oracle Text - лучший ответ для решения вашей проблемы.

И если вы используете базу данных, то имеет смысл позволить dbms выполнять вычисления для вас. Это почти всегда будет быстрее, чем извлечение данных.

Почему Oracle Text (например) превосходит самореализованные алгоритмы: Oracle имеет понятие "темы", например, он знает, что слово "политика" связано с "выборами", Для этого используется база знаний. (Просто прочитайте документацию, и вы будете удивлены). Вы потратили годы, чтобы развить его с нуля.