Оценка сходства строк/хеш

Ответ 1

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

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

Ответ 2

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

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

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

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

Ответ 3

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

Одним из способов удаления удаленных слов является индексирование 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-грамм. Это уменьшает количество кандидатов до разумной суммы, и вы можете продолжить заданную строку levenstein для каждого из левых кандидатов.

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

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

Ответ 4

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

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

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

• A Bursted Trie с компактностью уровня
• Левенштейн Автомат

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

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

Ответ 5

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

Ответ 6

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

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

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

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

Ответ 7

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

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

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' ]

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

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

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

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

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

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

Если вы согласны с тем, что проблема высока, вы можете сохранить свои строки в метрическом дереве wikipedia: метрическое дерево. Это ограничило бы ваше пространство поиска, но не решило бы ваше решение "одного номера".

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

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

Изменить расстояние или расстояние Левенштейна

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

Ответ 8

Я думаю о чем-то вроде этого:

• удалить все символы без слова
• применить soundex

Ответ 9

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

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

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

Ответ 10

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

Просто идея.

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

Ответ 11

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

{"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!"

Это несколько дало оценку каждой строке вашей коллекции строк
Реализация С# (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 - длина каждой строки
Более подробную информацию о минимальном расстоянии редактирования можно найти здесь

Ответ 12

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

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