soundex算法的数据结构？

Question

谁能建议我在 soundex 算法 程序中使用什么数据结构？ 使用的语言是Java。 如果有人以前用 Java 做过这个工作。 该程序应具有以下功能： 能够阅读约50,000字 应该能够读取一个单词并返回具有相同 soundex 的相关单词

我不希望程序实现只是关于使用什么数据结构的一些建议。

Answer 1

提示：如果您使用 SQL 作为数据后端，那么您可以让 SQL 使用两个 sql 函数 SOUNDEX 和 DIFFERENCE 来处理它。

也许不是你想要的，但很多人不知道MSsql有这两个功能。

Answer 2

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($_)};
        }
}

Answer 3

我相信你只需要将原始字符串转换为 soundex 键并转换为哈希表即可； 表中每个条目的值将是映射到该 soundex 的原始字符串的集合。

Google 集合中的 MultiMap 集合接口（及其实现）会对您有用。

Answer 4

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 5

由于 soundex 是一个哈希，因此我将使用哈希表，以 soundex 作为键。

Answer 6

你想要一个 4 字节整数。

soundex 算法始终返回 4 个字符的代码，如果您使用 ANSI 输入，您将得到 4 个字节（表示为 4 个字母）。

因此，将返回的代码存储在哈希表中，将单词转换为代码并在哈希表中查找。 真的就是这么简单。