Эффективно постройте график слов с заданным расстоянием Хэмминга

Ответ 1

Предполагая, что вы храните словарь в set(), так что поиск O (1) в среднем (худший case O (n)).

Вы можете сгенерировать все допустимые слова на расстоянии 1 от слова:

>>> def neighbours(word):
...     for j in range(len(word)):
...         for d in string.ascii_lowercase:
...             word1 = ''.join(d if i==j else c for i,c in enumerate(word))
...             if word1 != word and word1 in words: yield word1
...
>>> {word: list(neighbours(word)) for word in words}
{'bot': ['lot'], 'lol': ['lot'], 'lot': ['bot', 'lol']}

Если M - длина слова, L длина алфавита (т.е. 26), сложность времени наихудшего случая поиск соседних слов при таком подходе O (L * M * N).

Временная сложность подхода "простой путь" O (N ^ 2).

Когда этот подход лучше? Когда L*M < N, т.е. Если рассматривать только строчные буквы, когда M < N/26. (Я рассматривал здесь только худший случай)

Примечание: средняя длина английского слова составляет 5.1 буквы. Таким образом, вы должны рассмотреть этот подход, если размер словаря превышает 132 слова.

Вероятно, можно добиться большей производительности, чем это. Однако это было действительно просто реализовать.

Экспериментальный ориентир:

Алгоритм "простого пути" (A1):

from itertools import zip_longest
def hammingdist(w1,w2): return sum(1 if c1!=c2 else 0 for c1,c2 in zip_longest(w1,w2))
def graph1(words): return {word: [n for n in words if hammingdist(word,n) == 1] for word in words}

Этот алгоритм (A2):

def graph2(words): return {word: list(neighbours(word)) for word in words}

Код бенчмаркинга:

for dict_size in range(100,6000,100):
    words = set([''.join(random.choice(string.ascii_lowercase) for x in range(3)) for _ in range(dict_size)])
    t1 = Timer(lambda: graph1()).timeit(10)
    t2 = Timer(lambda: graph2()).timeit(10)
    print('%d,%f,%f' % (dict_size,t1,t2))

Вывод:

100,0.119276,0.136940
200,0.459325,0.233766
300,0.958735,0.325848
400,1.706914,0.446965
500,2.744136,0.545569
600,3.748029,0.682245
700,5.443656,0.773449
800,6.773326,0.874296
900,8.535195,0.996929
1000,10.445875,1.126241
1100,12.510936,1.179570
...

Я провел еще один тест с меньшими шагами N, чтобы увидеть его ближе:

10,0.002243,0.026343
20,0.010982,0.070572
30,0.023949,0.073169
40,0.035697,0.090908
50,0.057658,0.114725
60,0.079863,0.135462
70,0.107428,0.159410
80,0.142211,0.176512
90,0.182526,0.210243
100,0.217721,0.218544
110,0.268710,0.256711
120,0.334201,0.268040
130,0.383052,0.291999
140,0.427078,0.312975
150,0.501833,0.338531
160,0.637434,0.355136
170,0.635296,0.369626
180,0.698631,0.400146
190,0.904568,0.444710
200,1.024610,0.486549
210,1.008412,0.459280
220,1.056356,0.501408
...

Вы видите, что компромисс очень низок (100 для словарей слов с длиной = 3). Для небольших словарей алгоритм O (N ^ 2) работает немного лучше, но это легко бить алгоритмом O (LMN) по мере роста N.

Для словарей с более длинными словами алгоритм O (LMN) остается линейным в N, он просто имеет другой наклон, поэтому компромисс движется немного вправо (130 для длины = 5).

Ответ 2

Нет необходимости брать зависимость от размера алфавита. Например, слово bot вставляет его в словарь списков слов под клавишами ?ot, b?t, bo?. Затем для каждого списка слов соедините все пары.

import collections


d = collections.defaultdict(list)
with open('/usr/share/dict/words') as f:
    for line in f:
        for word in line.split():
            if len(word) == 6:
                for i in range(len(word)):
                    d[word[:i] + ' ' + word[i + 1:]].append(word)
pairs = [(word1, word2) for s in d.values() for word1 in s for word2 in s if word1 < word2]
print(len(pairs))

Ответ 3

Trainary Search Trie поддерживает поиск ближнего ближнего боя довольно хорошо.

Если ваш словарь хранится как TST, то, полагаю, средняя сложность поиска при построении графика будет близка к O(N*log(N)) в словарях реального мира.

И проверьте Эффективное автоматическое заполнение с помощью трехмерной статьи дерева поиска.

Ответ 4

Здесь представлен линейный алгоритм O (N), но с большим постоянным множителем (R * L * 2). R - радиус (для латинского алфавита - 26). L - средняя длина слова. 2 является фактором добавления/замены подстановочного символа. Таким образом, abc, aac и abca - два операционных устройства, которые приводят к расстоянию от помех до 1.

Это написано в Ruby. И для 240k слов требуется ~ 250 Мб ОЗУ и 136 секунд в среднем аппаратном обеспечении

Схема реализации графика

class Node
  attr_reader :val, :edges

  def initialize(val)
    @val = val
    @edges = {}
  end

  def <<(node)
    @edges[node.val] ||= true
  end

  def connected?(node)
    @edges[node.val]
  end

  def inspect
    "Val: #{@val}, edges: #{@edges.keys * ', '}"
  end
end

class Graph
  attr_reader :vertices
  def initialize
    @vertices = {}
  end

  def <<(val)
    @vertices[val] = Node.new(val)
  end

  def connect(node1, node2)
    # print "connecting #{size} #{node1.val}, #{node2.val}\r"
    node1 << node2
    node2 << node1
  end

  def each
    @vertices.each do |val, node|
      yield [val, node]
    end
  end

  def get(val)
    @vertices[val]
  end
end

Сам алгоритм

CHARACTERS = ('a'..'z').to_a
graph = Graph.new

# ~ 240 000 words
File.read("/usr/share/dict/words").each_line.each do |word|
  word = word.chomp
  graph << word.downcase
end

graph.each do |val, node|
  CHARACTERS.each do |char|
    i = 0
    while i <= val.size
      node2 = graph.get(val[0, i] + char + val[i..-1])
      graph.connect(node, node2) if node2
      if i < val.size
        node2 = graph.get(val[0, i] + char + val[i+1..-1])
        graph.connect(node, node2) if node2
      end
      i += 1
    end
  end
end