Структура данных для алгоритма soundex?

Question

Может ли кто-нибудь предложить мне, какую структуру данных использовать для программы soundex algorithm? Язык, который будет использоваться, - Java. Если кто-то работал над этим раньше в Java. Программа должны иметь следующие характеристики: быть в состоянии прочитать около 50000 слов должны быть в состоянии прочитать слова и вернуть родственные слова, имеющие один и тот же Soundex

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

Answer 1

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

Интерфейс коллекции MultiMap (и его реализации) в Google Collections будет вам полезен.

Answer 2

СОВЕТ. Если вы используете SQL как базу данных, вы можете позволить SQL обрабатывать ее с помощью двух SQL-функций SOUNDEX и DIFFERENCE.

Возможно, не то, что вы хотели, но многие люди не знают, что MSsql имеет эти две функции.

Answer 3

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

После этого 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($_)}; 
     } 
} 

Answer 4

Поскольку Саундэкс хэш, я хотел бы использовать хэш-таблицу, с Soundex в качестве ключа.

Answer 5

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 или что у вас есть. Некоторые стратегии могут быть перестраиваемыми (количество символов выводится и т. Д.)

Answer 6

вы хотите 4-байтовое целое число.

Алгоритм soundex всегда возвращает 4-символьный код, если вы используете входы ANSI, вы получите обратно 4 байта (представлены как 4 буквы).

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