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

Question

считают, что у меня есть

string1 = "hello hi goodmorning evening [...]"

и у меня есть несколько незначительных ключевых слов

compare1 = "hello evening"
compare2 = "hello hi"

Мне нужна функция, которая возвращает сходство между текстом и ключевыми словами. Пример:

function(string1,compare1);  // returns: 4
function(string1,compare2);  // returns: 5 (more relevant)

Обратите внимание, что 5 и 4 приведены только для примера.

Вы могли бы сказать - написать функцию, которая подсчитывает вхождения, но для этого примера это не сработает, потому что оба получили 2 вхождения, но сравнение1 менее актуально, потому что "привет вечер" точно не найден в строке1 (2 слова привет и вечер более далек, чем привет привет *

есть какой-нибудь известный алгоритм для этого?

ADD1:

алгоритмы типа Edit Distance в этом случае НЕ будут работать. Поскольку строка1 представляет собой полный текст (например, 300-400 слов), а сравниваемые строки - максимум 4-5 слов.

Answer 1

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

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

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

Алгоритм был впервые предложен Темплом Ф. Смитом и Майклом С. Уотерманом в 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!

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

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

Answer 2

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

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

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

Answer 3

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

Answer 4

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

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

Answer 5

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

Расстояниебудет затем сумма следующих значений:

• Все подстадии
• Количество пробелов минус один в каждом наборе последовательных вставок / удалений:
  • (В вашемcase: "hi goodmorning" считается только двумя правками, а [[]] считается одним.)

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

РЕДАКТИРОВАТЬ

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

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

Answer 6

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

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

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

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

Answer 7

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

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

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

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