用一个高效的方法制作字典图表

Question

什么是以汉明距离=1为标准制作词典单词图表的最有效方法？

- copperhead

---

你想要整个字典的“一个”图表，还是从某个单词开始的图表？ - Dr. belisarius

每个问题的解决方案应该是什么？ - copperhead

那是两个问题！ :) - Dr. belisarius

从一个单词开始的图。 - copperhead

@belisarius 嗯？他想要一个单词哈明距离为1的图表。从哪里开始并不重要 - 最终的图表将是相同的。 - Nick Johnson

@Nick 我试图表达的是从某一点开始的“一个连通图”与你的字典中的“所有连通子图”。也许我没有表达清楚。 - Dr. belisarius

Answer 1

汉明距离只适用于长度相等的单词，因此您的字典中每个单词长度都会有一个不相交的图。如果您指的是可以插入和删除的莱文斯坦距离，则确实会有一个单独的图。

一种选择是从您的字典构建BK-tree。虽然严格来说不是图，但它允许您提出同样的问题（获取具有给定距离的元素列表），并且需要O(n log n)时间来构建。

另一种选择是暴力方法：对于每个单词，测试其与所有候选单词的距离。您可以将候选单词缩小到相同长度（或长度少一或多一，对于莱文斯坦距离）。这是最坏情况下的O(n^2)，但如果您不止一次构建图，则可能是可以接受的。

理论上，可能存在一种O(n log n)构建图的方法-在平凡的情况下，构建BK树，然后从该树生成图的时间复杂度为O(mn log n)，其中m是每个节点的平均边数-但我不知道是否有优雅的方法。

- Nick Johnson

---

暴力破解方法实际上是O(n^2 * l)，其中l是字典中单词的最大长度。由于字典中有n个单词，因此l至少为log n / log 26，因此暴力破解方法在最好情况下为O(n^2 log n)。 - Chris Hopman

假设哈希集合查找和插入是恒定的，并且字母表有26个字符。构建一个包含字典中所有内容的哈希集合 - O(n * l)。对于字典中的每个单词，在哈希集合中查找该单词的l * 25个可能的汉明邻居（l * 50左右的莱文斯坦邻居）- O(n * l * l)。如果l ~ log(n)，则总体上这是O(n (log n)^2)。 - Chris Hopman

Answer 2

我建议使用邻接映射 map<string, list<string> 来表示图形。它将图形节点（在我们的情况下是单词）映射到相邻节点的列表（即距离==1的所有单词）。

如何填充此映射？首先，将字典分解为相同长度的单词集合 set<string> wordset[MAX_WORD_LENGTH]，然后按以下方式填充映射。

map<string, list<string>> adjacency_map
for each wordset in wordset array  
  for each w1 in wordset
     for each w2 in wordset
        if one_char_off(w1, w2) { // if the distance between w1 and w2 == 1
           update(adjacency_map, w1, w2)
           update(adjacency_map, w2, w1)
        }

Function one_char_off(string w1, string w2) checks if the distance between w1 and w2 is 1.

int diff = 0
for i in [0, w1.length) // both w1 and w2 have the same length
   if w1[i] != w2[i]
      if ++diff > 1
         return false
return diff == 1

函数 update(map<string, list<string>> adjacency_map, string w1, string w2) 将相邻单词对 w1 和 w2 添加到相邻映射中。

- Michael