Может ли кто-нибудь подсказать мне, какую структуру данных использовать для программы алгоритма soundex? Используемый язык - Java. Если кто-нибудь работал над этим раньше на Java. Программа должна иметь следующие функции: уметь читать около 50 000 слов; уметь читать слово и возвращать связанные слова с таким же звуковым индексом.
Я не хочу, чтобы реализация программы давала лишь несколько советов о том, какую структуру данных использовать.
СОВЕТ: Если вы используете SQL как базу данных, вы можете позволить SQL обрабатывать его с помощью двух sql-функций SOUNDEX и DIFFERENCE.
Возможно, это не то, что вы хотели, но многие люди не знают, что MSsql имеет эти две функции.
Ну, soundex может быть реализован простым проходом по строке, так что для этого не требуется ничего особенного.
После этого 4-символьный код можно рассматривать как целочисленный ключ.
Затем просто создайте словарь, в котором хранятся наборы слов, проиндексированные этим целочисленным ключом. 50 000 слов должны легко уместиться в памяти, поэтому ничего особенного не требуется.
Затем пройдитесь по словарю, и каждое ведро представляет собой группу похожих по звучанию слов.
Собственно, вот вся программа на perl:
#!/usr/bin/perl
use Text::Soundex;
use Data::Dumper;
open(DICT,"</usr/share/dict/linux.words");
my %dictionary = ();
while (<DICT>) {
chomp();
chomp();
push @{$dictionary{soundex($_)}},$_;
}
close(DICT);
while (<>) {
my @words = split / +/;
foreach (@words) {
print Dumper $dictionary{soundex($_)};
}
}
Я считаю, что вам просто нужно преобразовать исходные строки в soundex-ключи в хеш-таблицу; значение для каждой записи в таблице будет набором исходных строк, сопоставленных с этим звуковым индексом.
Вам будет полезен интерфейс коллекции MultiMap (и его реализации) в Google Collections .
class SpellChecker
{
interface Hash {
String hash(String);
}
private final Hash hash;
private final Map<String, Set<String>> collisions;
SpellChecker(Hash hash) {
this.hash = hash;
collisions = new TreeSet<String, Set<String>>();
}
boolean addWord(String word) {
String key = hash.hash(word);
Set<String> similar = collisions.get(key);
if (similar == null)
collisions.put(key, similar = new TreeSet<String>());
return similar.add(word);
}
Set<String> similar(String word) {
Set<String> similar = collisions.get(hash.hash(word));
if (similar == null)
return Collections.emptySet();
else
return Collections.unmodifiableSet(similar);
}
}
Стратегия хеширования может быть Soundex, Metaphone или что-то еще. Некоторые стратегии можно настраивать (сколько символов выводится и т. Д.)
Поскольку soundex - это хэш, я бы использовал хеш-таблицу с soundex в качестве ключа.
вам нужно 4-байтовое целое число.
Алгоритм soundex всегда возвращает 4-символьный код, если вы используете входные данные ANSI, вы получите 4-байта назад (представленные 4 буквами).
Так что сохраните коды, возвращенные в хеш-таблице, преобразуйте свое слово в код и найдите его в хеш-таблице. Это действительно так просто.
