Autocomplete

Description

The Dictionary struct stores a collection of words, each with its corresponding weight. In this structure, each word is represented as a path within a tree, where each node along the path corresponds to a character in the word. Terminal nodes hold both the word itself and its weight.

These terminal nodes store the complete word to expedite lookups, eliminating the need for backtracking and reconstructing the word from individual characters. Weights are used to arrange entries within the resulting vector, wherein words with greater weight will be positioned at the beginning.

pub struct Dictionary<T> {
    entries: BTreeMap<char, Dictionary<T>>,
    terminal: Option<Terminal<T>>,
}

struct Terminal<T> {
    weight: T,
    word: String,
}

For example, words

A, 1
AA, 5
ABC, 3

Would be represented as

Dictionary {
    terminal: None,
    entries: {
        'A': Dictionary {
            terminal: Some({
                weight: 1,
                word: "A",
            })
            entries: {
                'A': Dictionary {
                    terminal: Some({
                        weight: 5,
                        word: "AA"
                    }),
                    entries: {},
                },
                'B': Dictionary {
                    terminal: None,
                    entries: {
                        'C': Dictionary {
                            termainal: Some({
                                weight: 3,
                                word: "ABC",
                            })
                            entries: {},
                        },
                    },
                },
            },
        },
    },
}

Usage

Both build and build_without_weights methods provide a convenient way to initialize and construct a Dictionary object from a list of words, either with or without weights. These methods abstract away the details of manually inserting each word into the dictionary, making it easier to create and work with Dictionary objects in your code.

// Example using build method
let words_with_weights = vec![
    ("A".to_string(), 1),
    ("AA".to_string(), 5),
    ("ABC".to_string(), 3),
];

let dictionary = Dictionary::<usize>::build(words_with_weights);

// Example using build_without_weights method
let words = vec![
    "A".to_string(),
    "AA".to_string(),
    "ABC".to_string(),
];

let dictionary_unweighted = Dictionary::<usize>::build_without_weights(words);

To query the Dictionary by prefix, use words methods.

// Example using words
dictionary.words("A")
// [
//     ("AA", 5), 
//     ("ABC", 3), 
//     ("A", 1), 
// ]

Installation

The package is available at crates.io

License

This project is licensed under the MIT license. Please see the LICENSE file for more details.