Самый короткий путь между двумя узлами Trie

Question

Это двоякий вопрос, потому что у меня нет идей о том, как реализовать это наиболее эффективно.

У меня есть словарь 150000 слов, которые хранятся в реализации Trie, вот что выглядит моя конкретная реализация, как:

Пользователь дается с двумя словами. С целью найти кратчайший путь других английских слов (измененных одним символом за штуку) от стартового слова до конечного слова.

Например:

Старт: Собака

Конец: Cat

Путь: Собака, Dot, раскладушка, Cat

Путь: Собака, зубчатая, лаг, Болото, Bot, Cot, Cat

Путь: Собака, Doe, Joe, Joy, Jot, Cot, Cat

---

Моя текущая реализация прошла несколько итераций, но самый простой, я могу предоставить псевдокод для (как фактический код несколько файлов):

var start = "dog"; 
var end = "cat"; 
var alphabet = [a, b, c, d, e .... y, z]; 
var possible_words = []; 

for (var letter_of_word = 0; letter_of_word < start.length; letter_of_word++) { 
    for (var letter_of_alphabet = 0; letter_of_alphabet < alphabet.length; letter_of_alphabet++) { 
     var new_word = start; 
     new_word.characterAt(letter_of_word) = alphabet[letter_of_alphabet]; 
     if (in_dictionary(new_word)) { 
      add_to.possible_words; 
     } 
    } 
} 

function bfs() { 
    var q = []; 
    ... usual bfs implementation here .. 
} 

---

Knowns:

• Начальное слово и слово завершения
• слова одинакового размера
• Слова английские слова
• Вполне возможно, там не может быть путь

---

Вопрос:

Мой вопрос я не эффективный способ определения того, потенциальное слово, чтобы попытаться без грубого форсирования алфавита и проверки каждого нового слова против словаря. Я знаю, что есть возможность более эффективного использования префиксов, но я не могу понять правильную реализацию или не просто удвоить обработку.

Во-вторых, следует ли использовать другой алгоритм поиска, я рассматривал A * и Best First Search как возможности, но для них требуются веса, которых у меня нет.

Мысли?

Answer 1

Как указано в комментариях, иллюстрируя, что я имею в виду, кодируя связанные слова в битах целых чисел.

В C++ это может выглядеть примерно так ...

// populate a list of known words (or read from file etc)... 
std::vector<std::string> words = { 
    "dog", "dot", "cot", "cat", "log", "bog" 
}; 

// create sets of one-letter-apart words... 
std::unordered_map<std::string, int32_t> links; 
for (auto& word : words) 
    for (int i = 0; i < word.size(); ++i) 
    { 
     char save = word[i]; 
     word[i] = '_'; 
     links[word] |= 1 << (save - 'a'); 
     word[i] = save; 
    } 

После выполнения приведенный выше код, links[x] - где x это слово с одной буквой заменяется подчеркиванием а-ля d_g - возвращает целое число, указывающее буквы, которые могут заменить подчеркивание, чтобы сформировать известные слова. Если младший значащий бит включен, тогда слово «dag» является известным словом, если бит-бит следующего-наименьшего значения включен, тогда «dbg» - это известное слово и т. Д.

Интуитивно я ожидаю использования целые числа, чтобы уменьшить общую память, используемую для данных привязки, но если в большинстве слов имеется только несколько связанных слов, хранение некоторого индекса или указателя на эти слова может фактически использовать меньше памяти - и быть проще, если вы не используете побитовые манипуляции , то есть:

std::unordered_map<std::string, std::vector<const char*>> links; 
for (auto& word : words) 
    for (int i = 0; i < word.size(); ++i) 
    { 
     char save = word[i]; 
     word[i] = '_'; 
     links[word].push_back(word.c_str()); 
     word[i] = save; 
    } 

в любом случае, вы затем граф, связывающий каждое слово тем, она может превратиться в с изменениями односимвольных. Затем вы можете применить логику Dijkstra's algorithm, чтобы найти кратчайший путь между любыми двумя словами.

Answer 2

Чтобы добавить обновление для тех, кто снял этот вопрос, я добавил репозиторий Github для реализации в Javascript для этой конкретной структуры данных.

https://github.com/acupajoe/Lexibit.js

Спасибо всем за помощь и идеи!