Разработка Оксфордского словаря английского языка

Question

В одном из интервью меня спросили, как мне составить Оксфордский словарь английского языка.

Я сказал ему, что буду использовать структуру данных TREE, но он ответил, что это займет много памяти.Итак, какую другую структуру данных следует использовать?

Answer 1

Одна структура данных, которую я слышал, использовалась в прошлом в мобильных телефонах для хранения словарей T9, является следующей (ну, это касается только ключевой проблемы, но не хранилища определений):

Записи отсортированы,и каждая запись должна начинаться со смещения в предыдущей записи, откуда она должна быть продолжена, а также продолжения.Например:

apple
4icable
7tion

будет декодироваться в Apple, в зависимости от применения.Однако это может не сильно отличаться от попыток с объединенными цепями, см.

appl -> e 
     -> ica -> ble
            -> tion

Википедия раскрыла Направленный ациклический граф слов , который отличается от деревьев тем, что он не только разветвляется, но и разветвляется.объединить, где слова имеют одинаковый суффикс.Это действительно может быть превосходное хранилище.

        a
       / \
  pplic   utom
       \ /
      ation

Answer 2

Как уже упоминали другие, если не хватает крыши для хорошо спроектированного дерева, вероятно, нет места и для любого другого вида индекса.Поскольку речь идет о вопросе для интервью, похоже, он пытался направить вас к классическим неструктурным структурам данных, таким как B-деревья.

С другой стороны, хорошим ответом может быть запрос дополнительной информации,например, «какие операции вы хотите выполнить в этой структуре данных и какую производительность вам нужно?»Если вы просто хотите проверить орфографию, тогда фильтр Блума может быть самой эффективной "структурой данных" ...

Answer 3

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