Структура данных для поиска строк

Question

Я ищу лучшую структуру данных для следующего случая: В моем случае у меня будет тысячи строк, однако для этого примера я буду использовать два по понятным причинам. Итак, скажем, у меня есть строки «Вода» и «Уолтер», мне нужно, чтобы в букву «W» вводились обе строки, которые нужно найти, и когда «Wat» вводится «Water», чтобы быть единственным результатом. Я сделал исследование, но я все еще не совсем уверен, какая правильная структура данных для этого случая, и я не хочу ее реализовывать, если не уверен, что это будет тратить время. Так что в основном то, что я сейчас думаю, это либо «Trie», либо «Suffix Tree». Похоже, что «Trie» будет делать трюк, но, как я сказал, мне нужно быть уверенным. Кроме того, реализация не должна быть проблемой, поэтому мне просто нужно знать правильную структуру. Также не стесняйтесь сообщать мне, есть ли лучший выбор. Как вы можете догадаться, нормальные структуры, такие как Dictionary/MultiDictionary, не будут работать, так как это будет убийца памяти. Я также планирую реализовать кеш, чтобы ограничить потребление памяти. Я сожалею, что нет кода, но я надеюсь, что я получу ответ. Заранее спасибо.

Answer 1

Вы должны связаться с пользователем Trie. Tries являются основой для одного из самых быстрых известных алгоритмов сортировки (burstsort), он также используется для проверки орфографии и используется в приложениях, которые используют завершение текста. Вы можете увидеть детали here.

Answer 2

Практически, если вы хотите сделать автоматическое предложение, то достаточно хранить до 3-4 символов. Я имею в виду предлагать, когда и когда пользователь вводит «a» или «ab» или «abc», и когда он набирает «abcd» или более символов, вы можете использовать map.keys, начинающиеся с «abcd», с использованием ладских выражений языка C#.

Таким образом, я предлагаю, создать карту, как: Карты < полукокса, < < Карты полукокса, Карта < полукокса, Set < строки >>>>> карты; Итак, если пользователь вводит «a», вы ищете карту [a] и найдете всех детей.