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

Question

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

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

Answer 1

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

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

Answer 2

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

После этого 4-символьный код можно рассматривать как целочисленный ключ.

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

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

Собственно, вот и вся программа на 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 3

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 4

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

Интерфейс коллекции MultiMap (и его реализации) в Коллекциях Google был бы вам полезен.

Answer 5

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

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

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

Answer 6

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