Искатель слов Эрудит: создание дерева, хранение дерева, использование дерева? - PullRequest
Новая
       15

Искатель слов Эрудит: создание дерева, хранение дерева, использование дерева?

7 голосов
/ 16 сентября 2011

Что я пытаюсь сделать:

  • Создание мобильного веб-приложения, в котором пользователь может получить помощь в поиске слов для игры при игре в скрэббл
  • Пользователи получают подсказки слов, набирая любое количество букв и 0 или более подстановочных знаков

Как я пытаюсь это сделать:

  • Использование базы данных MySQL со словарем, содержащим более 400 тыс. Слов
  • Использование ASP.NET с C # в качестве языка программирования на стороне сервера
  • Использование HTML5, CSS и Javascript

Мой текущий план:

  • Создание Trie со всеми словами из базы данных, чтобы я мог выполнять быстрый и точный поиск слов в зависимости от ввода букв / подстановочных знаков пользователя

Наличие плана бесполезно, если вы не можете его выполнить, вот в чем мне нужна помощь:

  • Как мне построить Trie из базы данных? (ОБНОВЛЕНИЕ: я хочу сгенерировать Trie, используя слова, уже имеющиеся в моей базе данных, после того, как это будет сделано, я больше не буду использовать базу данных для сопоставления слов)
  • Как сохранить Trie для быстрого и легкого доступа? (ОБНОВЛЕНИЕ: так что я могу удалить мою базу данных)
  • Как использовать C # для поиска слов с помощью Trie в зависимости от букв и подстановочных знаков?

Наконец:
Любая помощь очень ценится, я все еще начинающий с C # и MySQL, поэтому будьте осторожны

Спасибо большое!

1 Ответ

17 голосов
/ 16 сентября 2011

Прежде всего, давайте посмотрим на ограничения на проблему.Вы хотите сохранить список слов для игры в структуре данных, которая эффективно поддерживает проблему «анаграммы».То есть, учитывая "стойку" из n букв, все слова из n или меньше букв в списке слов, которые можно сделать из этой стойки.список слов будет составлять около 400 тыс. слов, и, вероятно, он будет содержать от одного до десяти мегабайт строковых данных в несжатом виде.

Три - это классическая структура данных, используемая для решения этой проблемы, поскольку она сочетает в себе эффективность памяти и поискэффективность.Со списком слов около 400 тыс. Слов разумной длины вы сможете сохранить это в памяти.(В отличие от решения, подобного b-дереву, в котором большая часть дерева хранится на диске, потому что он слишком велик, чтобы помещаться в память сразу.)

Три обычно не более чем26-арное дерево (при условии, что вы используете латинский алфавит), где у каждого узла есть буква и один дополнительный бит на каждом узле, который говорит, является ли это концом слова.

Итак, давайте набросаем структуру данных: 

class TrieNode
{
    char Letter;
    bool IsEndOfWord;
    List<TrieNode> children; 
}

Это, конечно, просто набросок;вы, вероятно, захотите сделать так, чтобы у них были правильные методы доступа и конструкторы и тому подобное.Кроме того, возможно, плоский список не является лучшей структурой данных;может быть, какой-то словарь лучше.Мой совет - сначала запустите его, а затем измерьте его производительность, а если это неприемлемо, то поэкспериментируйте с внесением изменений, чтобы улучшить его производительность.

Вы можете начать с пустого дерева: 

TrieNode root = new TrieNode('^', false, new List<TrieNode>());

То есть это «корневой» узел дерева, который представляет начало слова.

Как добавить слово «AA», первое слово в словаре скрэббл?Что ж, сначала сделайте узел для первой буквы: 

root.Children.Add('A', false, new List<TrieNode>());

ОК, наш три теперь 

^
|
A

Теперь добавьте узел для второй буквы: 

root.Children[0].Children.Add(new trieNode('A', true, new List<TrieNode>()));

Наш трек теперь 

^
|
A
|
A$   -- we notate the end of word flag with $

Отлично.Теперь предположим, что мы хотим добавить AB.У нас уже есть узел для «A», поэтому добавьте к нему узел «B $»: 

root.Children[0].Children.Add(new trieNode('B', true, new List<TrieNode>());

, и теперь у нас есть 

    ^
    |
    A
   / \
  A$   B$

Продолжайте в том же духе.Конечно, вместо того, чтобы писать «root.Children [0] ...», вы напишите цикл, который ищет триан, чтобы увидеть, существует ли нужный вам узел, и если нет, создайте его.

Toсохранить ваше дерево на диске - честно говоря, я бы просто сохранил список слов в виде простого текстового файла и перестроил дерево, когда вам нужно.Это не должно занять более 30 секунд или около того, и тогда вы можете повторно использовать дерево в памяти.Если вы хотите сохранить файл в каком-то формате, который больше похож на файл, вам не составит труда найти формат сериализации.

Чтобы найти три на предмет соответствия стойки, идея состоит в том, чтобы исследовать каждую его часть, но исключить области, в которых стойка не может совпадать.Если у вас нет «А» на стойке, нет необходимости отключать любой «А» узел.Я набросал алгоритм поиска в вашем предыдущем вопросе.

У меня есть реализация постоянного функционального стиля, о котором я давно хотел написать, но так и не нашел его.Если я в конце концов опубликую это, я обновлю этот вопрос.

...