0

编辑 ：

我听从了你的好建议，并使用了 trie 数据结构来包含我的字典。我为感兴趣的人选择了这个结构。

但是现在我还有另一个问题：每次启动应用程序时构建的 trie 数据结构都非常长！也许我的字典太大了，或者我选择的 trie 的实现对于简单的字典来说太不合适了。

那么有没有办法在关闭应用程序（如注册数据库）之后保存这种结构，或者如果您认为问题是由实施引起的，您可以推荐我另一个吗？

我的android项目有一个严重的问题。

这里的目标是计算可以用一系列 6 个字母组成的所有单词

为此，我的 BDD 中有两个表：

  • 'words' 有两列：'_id' 和 'mots'
  • 和 'temp' 具有相同列的临时表。

'words' 包含词汇表中的所有单词（它很大），'temp' 包含可以用 6 个字母组成的所有可能的字母组合（至少使用 3 个字母）。

我正在尝试在“temp”表中选择真实的单词，以便在“words”表中选择单词。这是我的代码：

我首先选择包含好字母的单词（至少使用 3 个字母）

db.execSQL("CREATE TABLE temp2 (_id integer primary key autoincrement, mots text not null);");
db.execSQL("INSERT INTO temp2 (_id, mots) SELECT * FROM words WHERE mots like '%"+lettres.tab_char.get(0)+"%' OR mots like '%"+lettres.tab_char.get(1)+"%' "
                    + "OR mots like '%"+lettres.tab_char.get(2)+"%' OR mots like '%"+lettres.tab_char.get(3)+"%' OR mots like '%"+lettres.tab_char.get(4)+"%' "
                    + "OR mots like '%"+lettres.tab_char.get(5)+"%';");

（lettre.tab_char 是一个 ArrayList(Character)，其中包含用于在 temp 中进行组合的字母）

我在表 'temp2' 和 'temp' 之间进行连接：

String MY_QUERY = "SELECT temp2._id, temp2.mots FROM temp2 INNER JOIN temp ON temp2.mots = temp.mots;";
Cursor test =  db.rawQuery(MY_QUERY, null);

之后，我将我的值放入列表视图中。

它有效，但它真的很慢：你能帮帮我吗？

4

2 回答 2

1

通常，您使用的算法确实效率很低。首先，您使用通配符匹配搜索每个条目 6 次，然后再次将这个巨大的结果与整个数据集连接起来。

SQL 可能不是执行此操作的正确位置。SQL擅长查询，这更多的是计算。在代码中进行匹配。

有很多方法可以实现这一点，但找到正确的解决方案取决于您的要求。字母可以重复吗？“巨大”的词汇量有多大？它仍然适合几 MB 吗？这种查找是否需要几乎即时发生？

更新：

鉴于您的要求，我必须同意乔的观点。它实际上更像是一种数据结构，而不是算法，但 trie 是要走的路。您应该能够在加载应用程序时构建一次特里树，然后每个“匹配”都将是一个相当简单的沿着特里树的查找。

于 2011-06-20T23:58:30.387 回答
1

您正在寻找的算法实际上称为“ trie ”（re trie val 的缩写）。它们非常适合这种类型的计算（Android 实际上在 SMS 和邮件应用程序中使用它们来执行表情符号替换等操作）。如果做得好，您会惊讶于您可以从中获得的性能。我同意保罗的观点：你绝对不应该像现在这样进行查询。事实上，许多实现甚至会将整个字典文件加载到内存中的 trie 中，并在应用程序的整个生命周期中使用该 trie 进行单词查找和验证。拼字游戏单词列表（链接也包含在下面的问题中：twl06.zip) 只有 1.9MB，包含 178k 字。内存中的 trie 实际上应该比 1.9MB 小得多，因为多个单词将共享公共前缀（例如，“stair”和“stare”都将共享 STA 前缀，然后会分支成两个叶子 ["I" 和“R”]，等等……）

这是一个很好的起点：生成字谜的算法

于 2011-06-21T04:38:06.367 回答