Функция, возвращающая сходство между текстами?

Алгоритм динамического программирования

Кажется, то, что вы ищете, очень похоже на то, что Смит – Уотерман алгоритм делает.

Из Википедии:

Алгоритм был впервые предложен Темплом Ф. Смитом и Майклом С. Уотерманом в 1981 году. Подобно Needleman-Wunsch, разновидностью которого является алгоритм Смита-Уотермана, алгоритм динамического программирования . Таким образом, он обладает желаемым свойством, заключающимся в том, что он гарантирует оптимальное локальное выравнивание по отношению к используемой системе оценки (которая включает в себя матрицу замещения и схему оценки пробелов).

Давайте посмотрим на практический пример, чтобы вы могли оценить его полезность.

Допустим, у нас есть текст:

text = "We the people of the United States, in order to form a more 
perfect union, establish justice, insure domestic tranquility, 
provide for the common defense, 

  promote the general welfare, 

  and secure the blessings of liberty to ourselves and our posterity, 
do ordain and establish this Constitution for the United States of 
America.";  

Я выделил сегмент, который мы собираемся сопоставить, просто для удобства чтения.

Мы сравним сходство (или сходство) со списком строк:

list = {
   "the general welfare",
   "my personal welfare",
   "general utopian welfare",
   "the general",
   "promote welfare",
   "stackoverflow rulez"
   };  

У меня уже реализован алгоритм, поэтому я рассчитаю сходство и нормализую результаты:

sw = SmithWatermanSimilarity[ text, #] & /@ list;
swN = (sw - Min[sw])/(Max[sw] - Min[sw])  

Затем мы наносим результаты на график:

Думаю, это очень похоже на ваш ожидаемый результат.

HTH!

Некоторые реализации (с исходным кодом)

• Исходный код CUDA Smith-Waterman (GSW)
• Объяснение алгоритма S-M (презентация)
• Интерактивный пошаговый демонстрационный апплет
• Исходный код Java
• исходный код Python

Попробуйте создать N-граммы из ваших входных данных, а затем сопоставить N-граммы. У меня есть решение, в котором я рассматриваю каждую n-грамм как измерение в векторном пространстве (которое становится пространством из 4000 измерений в моем случае), а затем сродство - это косинус угла между двумя векторами (здесь задействовано точечное произведение ).

Сложнее всего придумать метрику, определяющую сродство так, как вы хотите.

Альтернативой является просмотр скользящего окна и оценка в зависимости от того, сколько слов в ваших данных compare_x находится в окне. Окончательный результат - это сумма.

py-editdist предоставит вам расстояние редактирования Левенштейна между двумя строками, которое может оказаться полезным. .

См .: http://www.mindrot.org/projects/py-editdist/

Пример кода с этой страницы:

import editdist

# Calculate the edit distance between two strings
d = editdist.distance("abc", "bcdef")

Связанный: https://stackoverflow.com/questions/682367/good-python-modules-for-fuzzy-string-comparison

Я думаю, что здесь есть довольно хороший и полный ответ на этот вопрос http://answers.google.com/answers/threadview?id=337832.

Извините за ответы Google!

Здесь вы можете найти список показателей для расчета расстояния между строками и java-библиотеку с открытым исходным кодом, которая просто делает это. http://en.wikipedia.org/wiki/String_metric В частности, обратите внимание на Алгоритм Смита – Уотермана, имея в виду, что то, что они называют «алфавитом», может быть составлено из того, что мы называем строками: итак, учитывая алфавит

{A = "hello", B = "hi",C = "goodmorning",D = "evening"}

и называется d расстоянием, ваша функция пытается вычислить

d(ABCD,AB) vs d(ABCD,AC)

Что ж, вы можете посчитать вхождения кусков сравниваемого текста, то есть:

«a-b-c» -> «a», «b», «c», «a-b», «b-c», «a-b-c» (возможно «a-c», если вы этого хотите)

А затем подсчитайте вхождения каждого из них и просуммируйте их, возможно, с весом (длина строки) / (длина всей строки).

Тогда вам просто нужен способ произвести эти части и провести проверку для всех из них.

Хотя расстояние Левенштейна в его нынешнем виде может не соответствовать вашим целям, его изменение может: Попробуйте реализовать это путем раздельного хранения вставок, удалений и замен.

Тогда расстояние будет суммой следующих величин:

• Все замены
• The number of spaces minus one in each set of consecutive insertions/deletions:
  • (In your case: " hi goodmorning " only counts as two edits, and ' [...] ' counts as one.)

Конечно, вам придется это протестировать, но если это не сработает, попробуйте просто использовать сумму последовательных вставок / удалений (так что «привет, доброе утро» - это всего лишь одно изменение).

ИЗМЕНИТЬ

P.S .: это предполагает относительно серьезные изменения в том, как работает Левенштейн, вам нужно сначала «выровнять» свои данные (выяснить, где существует значительное (более двух символов) перекрытие, и вставить «нулевые» символы, которые будут считаться вставками).

Кроме того, это всего лишь непроверенная идея, поэтому приветствуются любые идеи по улучшению.