эффективный способ составить график словаря

Question

Какой самый эффективный способ составить график слов в словаре с расстоянием Хэмминга = 1 ??

Answer 1

Расстояние Хэмминга определено только для слов одинаковой длины, поэтому у вас фактически будет один непересекающийся граф для каждой длины слова в вашем словаре. Если вы имели в виду расстояние levenshtein , которое разрешает вставки и удаления, то у вас действительно будет один график.

Один из вариантов - построить BK-дерево из вашего словаря. Хотя граф не является строго говоря, он позволяет вам задавать те же вопросы (получать список элементов с заданным расстоянием), и на его создание уходит O (n log n) времени.

Другой вариант - перебор: для каждого слова проверьте расстояние до всех слов-кандидатов. Вы можете сузить слова-кандидаты до слов одинаковой длины (или длины на один меньше или больше, для Левенштейна). Это O (n ^ 2) наихудший случай, но это может быть приемлемо, если вы строите график не более одного раза.

Теоретически, существует, вероятно, O (n log n) метод построения графа - в тривиальном случае построение BK-дерева с последующим генерированием графа из этого O (mn log n), где m - среднее количество ребер на узел - но я не знаю элегантного.

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)
        }

Функция one_char_off(string w1, string w2) проверяет, равно ли расстояние между w1 и w2 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 к соседней карте.