Оценка сходства строк / хэш - PullRequest
45 голосов
/ 01 декабря 2010

Есть ли метод для расчета чего-то вроде общего «показателя сходства» строки? Таким образом, я не сравниваю две строки вместе, а получаю некоторое число (хэш) для каждой строки, которое позже может сказать мне, что две строки похожи или не похожи. Две одинаковые строки должны иметь одинаковые (закрытые) хэши.

Давайте рассмотрим эти строки и оценки в качестве примера:

Hello world                1000
Hello world!               1010
Hello earth                1125
Foo bar                    3250
FooBarbar                  3750
Foo Bar!                   3300
Foo world!                 2350

Вы можете видеть, что Hello world! и Hello world похожи и их оценки близки друг к другу.

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

Ответы [ 12 ]

23 голосов
/ 18 января 2012

Я считаю, что то, что вы ищете, называется Locality Sensitive Hash . В то время как большинство алгоритмов хеширования спроектированы так, что небольшие изменения во входных данных вызывают большие изменения в выходных данных, эти хэши пытаются сделать обратное: небольшие изменения во входных данных генерируют пропорционально небольшие изменения в выходных данных.

Как уже упоминали другие, существуют проблемы, связанные с принуждением многомерного отображения к двумерному отображению. Это аналогично созданию плоской карты Земли ... вы никогда не сможете точно представить сферу на плоской поверхности. Лучшее, что вы можете сделать, - это найти LSH, оптимизированный для любой функции, которую вы используете, чтобы определить, «похожи» ли строки.

12 голосов
/ 16 апреля 2016

Расстояние Левенштейна или его производные - это тот алгоритм, который вам нужен. Сопоставьте данную строку с каждой из строк из словаря. (Здесь, если вам нужно только фиксированное количество наиболее похожих строк, вы можете использовать min-heap.) Если пробежка расстояния Левенштейна по всем строкам в словаре слишком дорога, используйте грубые Сначала алгоритм, который исключит слишком отдаленные слова из списка кандидатов. После этого пройдите дистанцию ​​Левенштейна по левым кандидатам.


Один из способов удалить отдаленные слова - индексировать n-граммы. Предварительно обработайте словарь, разбив каждое из слов на список n-граммов. Например, рассмотрим n = 3:

(0) "Hello world" -> ["Hel", "ell", "llo", "lo ", "o w", " wo", "wor", "orl", "rld"]
(1) "FooBarbar" -> ["Foo", "ooB", "oBa", "Bar", "arb", "rba", "bar"]
(2) "Foo world!" -> ["Foo", "oo ", "o w", " wo", "wor", "orl", "rld", "ld!"]

Далее создайте индекс n-граммов:

" wo" -> [0, 2]
"Bar" -> [1]
"Foo" -> [1, 2]
"Hel" -> [0]
"arb" -> [1]
"bar" -> [1]
"ell" -> [0]
"ld!" -> [2]
"llo" -> [0]
"lo " -> [0]
"o w" -> [0, 2]
"oBa" -> [1]
"oo " -> [2]
"ooB" -> [1]
"orl" -> [0, 2]
"rba" -> [1]
"rld" -> [0, 2]
"wor" -> [0, 2]

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


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

P.S. эта презентация кажется хорошим введением в вашу проблему.

11 голосов
/ 02 декабря 2010

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

Например, вы не можете назначить числа для этих трех фраз:

  • oneдва
  • один шесть
  • два шесть

Так, чтобы числа отражали разницу между всеми тремя фразами.

4 голосов
/ 01 декабря 2010

Хотя идея кажется очень милой ... Я никогда не слышал об этом.

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

Есть довольно проработанная техника, над которой я сейчас работаю:

  • Bursted Trie, с уровнем компактности
  • Автомат Левенштейна

Несмотря на то, что это не означает, что «невозможно» получить оценку, я почему-то думаю, что не было бы так много недавних исследований сравнений строк, если бы такой «метод» оценки оказался эффективным.

Если вы когда-нибудь найдете такой метод, я чрезвычайно заинтересован:)

2 голосов
/ 14 апреля 2016

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

Представьте себе сходство на уровне символов

stops
spots

hello world
world hello

В обоих примерах сообщения различны, но символы в сообщении идентичны, поэтому мера должна содержать значение позиции, а также символьное значение.(char 0 == 'h', char 1 == 'e' ...)

Затем сравните следующие похожие сообщения

hello world
ello world

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

В случае

spots
stops

Слова отличаются только положением символов, поэтому некоторая формапозиция важна.

Если следующие строки похожи

 yesssssssssssssss
 yessssssssssssss

Тогда у вас есть парадоксальная форма.Если вы добавите 2 s символов ко второй строке, она должна разделить расстояние, которое было до первой строки, но она должна быть отличной.Это можно повторить, получая постепенно более длинные строки, все из которых должны быть расположены ближе к строкам, только короче и длиннее их.Я не понимаю, как этого добиться.

В общем случае это рассматривается как многомерная проблема - разбить строку на вектор

[ 'h', 'e', 'l', 'l', 'o', ' ', 'w', 'o', 'r', 'l', 'd' ]

Но значения вектора могутне должно быть

  • , представленное числом с фиксированным размером, или
  • , обеспечивающее хорошую разницу в качестве.

Если количество слов или длина строкиограничены, тогда может быть возможным решение кодирования.

ограниченные значения

Используя что-то вроде арифметического сжатия, затем последовательность слов может быть преобразована в число с плавающей запятой, которое представляет последовательность.Однако это будет относиться к элементам ранее в последовательности как к более значимым, чем последний элемент в последовательности.

решение для интеллектуального анализа данных

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

У меня есть код для такого на github: кластеризация

Элементы, которые находятся близко друг к другу,должны храниться вместе в части дерева, но на самом деле нет никакой гарантии.Радиус поддеревьев используется для сокращения пространства поиска.

Редактировать расстояние или расстояние Левенштейна

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

2 голосов
/ 01 декабря 2010

Будет ли расстояние Левенштейна работать на вас?

1 голос
/ 02 декабря 2010

Возможно, используйте PCA , где матрица представляет собой список различий между строкой и фиксированным алфавитом (à la ABCDEFGHI ...).Ответом может быть просто длина основного компонента.

Просто идея.

готовый к запуску PCA на C #

1 голос
/ 01 декабря 2010

Ваша идея звучит как онтология , но применяется к целым фразам. Чем больше похожи две фразы, тем ближе они на графике (при условии, что вы используете взвешенные ребра). И наоборот: не похожие фразы очень далеки друг от друга.

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

И еще одна идея, основанная на расстоянии Левенштейна: вы можете сравнить n-граммы, которые дадут вам некоторый индекс сходства для двух данных фраз - чем больше они похожи, тем ближе значение к 1. Это можно использовать для вычисления расстояние на графике. написал статью об этом несколько лет назад, если вы хотите, я могу поделиться ею.

В любом случае: несмотря на то, что я не знаю точного решения, мне также интересно, что вы придумали.

0 голосов
/ 14 апреля 2016

В Обработка естественного языка У нас есть вещь, называемая Минимальное расстояние редактирования (также известное как Расстояние Левенштейна)
Он в основном определяется как наименьшее количество операций, необходимых для преобразования строки1 в строку2
Операции включены Вставка, Удаление, Замена , каждой операции присваивается оценка, к которой вы добавляете расстояние
Идея решения вашей проблемы состоит в том, чтобы вычислить MED из выбранной вами строки, ко всей другой строке, отсортировать эту коллекцию и выбрать n-ю первую наименьшую строку расстояния
Например:

{"Hello World", "Hello World!", "Hello Earth"}
Choosing base-string="Hello World"  
Med(base-string, "Hello World!") = 1  
Med(base-string, "Hello Earth") = 8  
1st closest string is "Hello World!"

Это несколько дало оценку каждой строке вашей коллекции строк
Реализация C # (Add-1, Deletion-1, Subsitution-2)

public static int Distance(string s1, string s2)
{
    int[,] matrix = new int[s1.Length + 1, s2.Length + 1];

    for (int i = 0; i <= s1.Length; i++)
        matrix[i, 0] = i;
    for (int i = 0; i <= s2.Length; i++)
        matrix[0, i] = i;

    for (int i = 1; i <= s1.Length; i++)
    {
        for (int j = 1; j <= s2.Length; j++)
        {
            int value1 = matrix[i - 1, j] + 1;
            int value2 = matrix[i, j - 1] + 1;
            int value3 = matrix[i - 1, j - 1] + ((s1[i - 1] == s2[j - 1]) ? 0 : 2);

            matrix[i, j] = Math.Min(value1, Math.Min(value2, value3));
        }
    }

    return matrix[s1.Length, s2.Length];
}

Сложность O (n x m) , где n, m - длина каждой строки
Более подробную информацию о минимальном расстоянии редактирования можно найти здесь

0 голосов
/ 01 декабря 2010

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

Число может развиваться так же по длине, как в интенсивность , но яЯ не уверен, что это очень поможет.

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

...