Сравнение имен композиторов, или Как найти «достаточно близкое» соответствие между двумя строками?

Question

После окончания двух классов CS я начал работать над личным проектом на Java. Я пишу программу, которая просматривает музыкальную коллекцию и пытается установить тег «Composer», просматривая имя файла и метатеги. Я сравниваю их со списком композиторов, который я создал в виде простого текстового файла. У меня вопрос такой:

Каков хороший метод для сравнения двух строк, чтобы попытаться найти наилучшее совпадение? Например, в моем случае предположим, что у меня есть файл под названием «Pulenc - Gloria in excelsis Deo.flac». В моем списке композиторов есть «Пуленк, Фрэнсис». Я хочу иметь возможность читать «Pulenc» и видеть, что он очень близок к «Poulenc», поэтому я могу правильно установить тег composer. Один мой друг предложил мне изучить косинусное расстояние (о котором я никогда не слышал), а другой порекомендовал расстояние Левенштейна. Является ли один из них хорошим подходом или есть другие методы, которые могут работать лучше?

Answer 1

Звучит так, будто Расстояние Левенштейна - это именно то, что вам нужно. Косинусное расстояние , кажется, имеет дело с более длинными текстами, а фонетические алгоритмы , такие как Soundex, вероятно, дадут плохие результаты для имен, большинство из которых не предназначены для произнесения с использованием правил английского произношения. 1007 *

Answer 2

Существует проект под названием SimMetrics , которым руководит Университет Шеффилда в Великобритании, который сможет вам помочь. Я немного написал об этом в своем блоге с точки зрения .NET, но я считаю, что в проекте также доступна реализация Java.

Answer 3

Я думаю, что в вашем случае Дамерау – Левенштейна e должно работать нормально. Если у вас есть больше данных, используйте их. При отсутствии хорошего алгоритма, большое количество данных может компенсировать это.

Answer 4

Кстати, в Apache Commons Lang lib реализован калькулятор Левенштейна: http://commons.apache.org/lang/api-release/org/apache/commons/lang/StringUtils.html#getLevenshteinDistance(java.lang.String,%20java.lang.String)

Answer 5

Питер Норвиг написал замечательную статью, "Как написать корректор орфографии" , которую вы можете найти полезной и которую можно настроить в соответствии с вашими конкретными потребностями.

Answer 6

Расстояние Левенштейна - разумная идея, хотя, если в вашей системе много композиторов, она может работать плохо. В отличие от Soundex (или Metaphone , или NYSIIS ), алгоритмы редактирования расстояния позволяют сравнивать имя вашего композитора с ошибкой и любое другое композитор в системе. В зависимости от того, сколько их, это может занять некоторое время.

В качестве (преждевременной?) Оптимизации, возможно, стоит рассчитать только расстояние Левенштейна для композиторов, чье имя начинается с правильной буквы.