Соответствие приблизительным строковым ключам на карте - PullRequest
Новая
       19

Соответствие приблизительным строковым ключам на карте

1 голос
/ 20 марта 2012

Кто-нибудь знает, есть ли хороший способ создать карту из строки в строку, имеющую приблизительные ключи строки? То есть, если я сделаю следующее: 

map.put("Fuzzy", "string")
map.put("Fuzy", "bear")

Я хочу, чтобы получилась карта: 

[ "Fuzzy":{ "string", "bear" } ]

(Там также может быть что-то, на что можно обратить внимание, что «медведь» происходит от «Fuzy», но это второстепенная проблема). Конечно, величина приближения (расстояния) между строками, вероятно, будет параметром. В этом случае расстояние равно 1, но оно может быть больше или меньше.

Насколько я могу судить, Trie может быть хорошим местом для начала, но я не хотел реализовывать что-то и найти, что это уже сделано.

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

Спасибо!

Ответы [ 3 ]

1 голос
/ 20 сентября 2013

Вот реализация FuzzyHashMap, хотя я еще не пробовал:

http://sourceforge.net/projects/fuzzyhashmap/

, а также реализация BK-Tree , которая выглядит связанной:

https://code.google.com/p/java-bk-tree/

1 голос
/ 20 марта 2012

Я бы предложил реализовать функции hashCode и equals, чтобы они возвращали Soundex объектов, которые вы храните на карте.

Тогда вы сможете быстро найти слова.

ОБНОВЛЕНИЕ: Я только что заметил, что похоже, что мы говорим на Python: так что вам нужно переопределить функцию __hash__ AFAIK (На также есть хороший пост о том, как реализовать хеш-карты в питоне )

0 голосов
/ 30 сентября 2014

У меня аналогичное требование, поэтому я реализовал свой собственный HashMap.

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

Моя хеш-функция:

первая часть хеш-кода хранит длину ключа вторая часть хеш-кода хранит сумму всех символов ключа

ширина битов этих двух частей фиксирована. Таким образом, мы получаем одно ведро для каждой длины ключа. В первом ведре хранятся ключи длиной 1, Во втором ведре хранятся ключи длиной 2, и так далее

Теперь, когда вызывается find (), 1. он проверяет точное совпадение. если найден, вернись. еще, перейдите к следующему шагу. 2. Существуют 3 варианта ошибок: искаженный символ, отсутствующий символ, дополнительный символ 3. проверьте наличие искаженного символа. искажения не меняют длину, поэтому мы должны искать то же самое ведро. если искажен один символ, значение хеша может увеличиваться или уменьшаться на MAX_CHAR_CODE при макс. Таким образом, от местоположения ожидаемого хэш-кода, ищите индексы MAX_CHAR_CODE вперед и назад. Большинство значений будет NULL. Когда найдено ненулевое значение, сравните ключи, допуская искажение одного символа. 4. проверьте наличие недостающего символа. если символ отсутствует, новая длина ключа будет меньше, чем фактическая. Поэтому нам нужно искать в следующем ведре. Суммарная часть хеш-кода уменьшилась бы на максимум MAX_CHAR_CODE. Так что поиск с текущей позиции в следующем сегменте, MAX_CHAR_CODE помещает вперед. Когда найдено значение, отличное от NULL, сравните ключи, допуская один пропущенный символ. 5. Дополнительный символ Очень похоже на 4.

...