АЛГОРИТМ - показатель сходства строк / хэш - PullRequest
Новая
       7

АЛГОРИТМ - показатель сходства строк / хэш

8 голосов
/ 12 июля 2011

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

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

Hello world 1000

Hello world!1010

Привет земля 1125

Foo bar 3250

FooBarbar 3750

Foo Bar!3300

Foo world!2350

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

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

Моя конечная цель: потоковые сообщения журнала (только чистые сообщения), и я хочу найти шаблон этих сообщений (какой-то тип регулярных выражений). Но это начинается только тогда, когда я могу собрать подобныестроки.Я снова сосредотачиваюсь на том, что я должен получить некоторое число / баллы (хэш) для каждой строки, и ТО, ЧТО МОЖЕТ ПОЗЖЕ сказать, что две строки являются или не похожи

Ответы [ 8 ]

6 голосов
/ 12 июля 2011

Взгляните на локально-зависимое хеширование .

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

Здесь есть очень хорошее объяснение здесь вместе с некоторым примером кода.

5 голосов
/ 13 июля 2011

TL; DR: Python BK-tree

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

В поисках некоторых терминов, связанных с этим, я нашел один особенно интересный тезис: Аспекты метрических пространств в вычислениях Мэтью Адам Скала.

На странице 26 он обсуждает меры сходства, основанные на kd-деревьях и других, но делает вывод:

Однако общие метрические пространства не обеспечивают геометрию, требуемую этими методами.Для общего метрического пространства без других предположений необходимо использовать дистанционный подход, основанный на дистанционном подходе, который индексирует точки исключительно на основе их расстояния друг от друга.Буркхард и Келлер [35] предложили одну из первых таких структур индексов, которая теперь известна как BK-дерево для их инициалов, в 1973 году. В BK-дереве предполагается, что метрика имеет несколько дискретных возвращаемых значений, каждый внутренний узелсодержит точку обзора, а поддеревья соответствуют различным значениям метрики.

Запись в блоге о том, как работают BK-деревья, можно найти здесь .

В диссертации Скала продолжает описывать другие решения этой проблемы, включая VP-деревья и GH-деревья.В главе 6 анализируются расстояния на основе расстояния редактирования Левенштейна.Он также представляет некоторые другие интересные метрики расстояния для строк.

Я также нашел Основы многомерных и метрических структур данных , которые, похоже, имеют отношение к вашему вопросу.

5 голосов
/ 12 июля 2011

Существует несколько таких «баллов», но все они зависят от того, как вы определяете сходство.

2 голосов
/ 12 июля 2011

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

1 голос
/ 04 августа 2015

Я не знаю, если вы все еще в этом, но в теории информации есть способ измерить, сколько информации имеет строка или кусок текста, возможно, вы могли бы использовать это значение в качестве хеша для сортировки строки. Это называется энтропия, и в Википедии есть хорошая статья об этом: https://en.wikipedia.org/wiki/Entropy_(information_theory)

1 голос
/ 30 апреля 2013

Возможно, вы захотите взглянуть на BK-Tree . Вот обсуждение и реализация Python .

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

1 голос
/ 12 июля 2011

Вы всегда можете использовать расстояние Левенштейна, для этого есть письменная реализация: http://code.google.com/p/pylevenshtein/

Но для простоты вы можете использовать встроенный модуль difflib: 

>>> import difflib
>>> l
{'Hello Earth', 'Hello World!', 'Foo Bar!', 'Foo world!', 'Foo bar', 'Hello World', 'FooBarbar'}
>>> difflib.get_close_matches("Foo World", l)
['Foo world!', 'Hello World', 'Hello World!']

http://docs.python.org/library/difflib.html#difflib.get_close_matches

0 голосов
/ 12 июля 2011

Вас может заинтересовать Расстояние Хэмминга .Функция Python hamming_distance () вычисляет расстояние Хемминга между двумя строками. 

def hamming_distance(s1, s2):
    assert len(s1) == len(s2)
    return sum(ch1 != ch2 for ch1, ch2 in zip(s1, s2))
...