汉明距离仅定义为相等长度的单词,因此您实际上在字典中每个单词长度都有一个不相交的图形.如果你的意思是levenshtein距离允许插入和删除,那么你确实会有一个图表.
一种选择是从字典中构造BK树.虽然严格来说不是图形,但它允许您提出相同的问题(获取具有给定距离的元素列表),并且需要O(n log n)时间来构造.
另一个选择是暴力:对于每个单词,测试它与所有候选单词的距离.你可以将候选词缩小到相同长度(或者levenshtein的长度减去或者更长).这是O(n ^ 2)最坏情况,但如果您不是多次构建图形,这可能是可以接受的.
从理论上讲,可能有一种构造图形的O(n log n)方法 - 在平凡的情况下,构造一个BK树,然后从中生成图形为O(mn log n),其中m是平均边数每个节点 - 但我不知道一个优雅的节点.