Мне нужно хранить разделенные '/' строки в древовидной структуре в C#, как мне это сделать?
Я пытаюсь сохранить части длинной строки в эффективной древовидной структуре, я искал, но большинство реализаций предназначены для поиска по словам... позвольте мне попытаться объяснить, что я имею в виду, на примере, если у меня есть:
/potato/carrot/tomato
/potato/carrot/pea
/potato/lettuce
Мои первые мысли были, что это должно выглядеть так
potato
- carrot
-tomato
-pea
- lettuce
и насколько я искал, действительно эффективные деревья поиска (такие как DAWG и Tries) предназначены для хранения слов в виде символов, и я не уверен, как мне поступить с ними. Есть идеи?
Заранее большое спасибо!
Редактировать: Что касается постоянства, мне не нужно хранить дерево, поэтому я подумал о том, чтобы сохранить его в памяти до тех пор, пока программа работает.
Edit2: Что касается хранения детей, я использовал HybridDictionaries, которые более эффективны, чем словари, и теперь все работает довольно быстро, большое спасибо, ребята!
2 ответа
Чтобы сохранить его в памяти, вы можете использовать этот шаблон, с которым я недавно столкнулся:
class Vegetable : Dictionary<string, List<Vegetable>>
В зависимости от того, что вы хотите с ним сделать (поиск, подсчет, сортировка), вы можете реализовать вспомогательные методы внутри этого класса.
Я думаю, что DAWG - хороший способ... взглянуть на этот проект, хотя он мог бы помочь с оптимизацией в C# и хотя ему несколько лет, алгоритм не изменился за это время.
Он содержит такой метод, как MakeDawg, FindNodeDepth и т. Д.
"Эта программа берет простой текстовый файл, состоящий только из строк из 26 строчных английских символов. Она генерирует дерево с префиксами и суффиксами, которое более эффективно, чем многие структуры данных, которые будут хранить ту же информацию. Этот код генератора очень Медленный, но он работает. Это может занять минуты. Его нужно оптимизировать, а алгоритм нуждается в улучшении, но я не приложил много усилий, потому что он не часто запускается в моих программах ".