Скачать trie - скачать исходный код trie

trie

Другой исходный код

v0.0.1

Скачать

попробовать

Реализация структуры данных Trie в Go. Он предоставляет больше возможностей, чем обычный поиск по префиксу Trie, и предназначен для автозаполнения.

Демо

Демо-версию WebAssembly можно попробовать по адресу shivamMg.github.io/trie.

Функции

Ключи представляют собой []string вместо string , тем самым поддерживая больше вариантов использования - например, []string{быстрая коричневая лиса} может быть ключом, где каждое слово будет узлом в Trie.
Поддержка ключа «Вставить» и «Удалить».
Поддержка поиска по префиксу — например, поиск по нации может вернуть нацию , национальный , национализм , националист и т. д.
Поддержка поиска по редактируемому расстоянию (также известному как расстояние Левенштейна) — например, поиск по слову «пшеница» может возвращать похожие слова, такие как «пшеница» , «чит» , «жара» , «что » и т. д.
Порядок результатов поиска является детерминированным. Это соответствует порядку вставки.

Примеры

 tri := trie.New()// Помещаем ключи ([]string) и значения (любые)tri.Put([]string{"the"}, 1)tri.Put([]string{"the", " быстрый", "коричневый", "лиса"}, 2)tri.Put([]string{"the", "быстрый", "спортивный", "автомобиль"}, 3)tri.Put([]string{" ", "зеленый", "дерево"}, 4)tri.Put([]string{"an", "apple", "tree"}, 5)tri.Put([]string{"an", "зонтик"} , 6)tri.Root().Print()// Вывод (полное дерево с терминалами, заканчивающимися на ($)):// ^// ├─ the ($)// │ ├─ fast// │ │ ├─ коричневый// │ │ │ └─ лиса ($)// │ │ └─ спортивный// │ │ └─ автомобиль ($)// │ └─ зеленый// │ └─ дерево ($)// └ ─ ан// ├─ яблоко// │ └─ дерево ($)// └─ зонтик ($)results := tri.Search([]string{"the", "quick"})for _, res := range results.Results { fmt.Println(res .Ключ, рез.Значение)
}// Вывод (поиск по префиксам):// [быстрая коричневая лиса] 2// [быстрая спортивная машина] 3key := []string{"the", "tree"}results = tri.Search(key , trie.WithMaxEditDistance(2), // Редактирование может быть вставкой, удалением, заменойtrie.WithEditOps())for _, res := range results.Results { fmt.Println(res.Key, res.EditDistance) // EditDistance — это количество правок, необходимых для преобразования в [дерево]}// Вывод (результаты не более чем на 2 правки от [дерева]):// [the ] 1// [зеленое дерево] 1// [яблоня] 2// [зонтик] 2result := results.Results[2]fmt.Printf("Преобразовать от %v до %v:n", result.Key, key)printEditOps(result.EditOps)// Вывод (операции редактирования, необходимые для преобразования результата в [дерево]):// Чтобы преобразовать [яблоню] в [ дерево]:// - удалить "an"// - заменить "apple" на "the"// - не редактировать "дерево"results = tri.Search(key, trie.WithMaxEditDistance(2), trie.WithTopKLeastEdited(), trie.WithMaxResults(2)) for _, res := range results.Results { fmt.Println(res.Key, res.Value, res.EditDistance)
}// Вывод (2 верхних наименее редактируемых результата):// [the] 1 1// [зеленое дерево] 4 1