strprox

strprox is a library that currently allows for top-k string autocompletion.

This is intended to implement the top-k "matching-based framework for error-tolerant autocompletion" algorithm from the paper by Deng et al. (see the Citations)

Table of Contents

• Example
• Notes
• Citations
• License
• Contributions

Example

use strprox::Autocompleter;

fn main() {
    // Here's the data that the autocompleter uses
    let source = vec![
        "success",
        "successive",
        "successor",
        "decrease",
        "decreasing",
        "decrement",
    ];
    let autocompleter = Autocompleter::new(&source);
    let query = "luck";

    // Retrieve the 3 best strings for autocompletion
    let result = autocompleter.autocomplete(query, 3);

    // The prefix edit distance is the best edit distance between a full string and
    // all the prefixes of another (refer to the paper by Deng et al.).
    //
    // Here the PED is between the query and the prefixes of the autocomplete strings.

    // (string: success, PED: 2)
    // (string: successive, PED: 2)
    // (string: successor, PED: 2)
    for measured_prefix in &result {
        println!("{}", measured_prefix);
    }

    // Collect the strings from the resulting string and prefix edit distance combination
    let result_strings: Vec<&str> = result
        .iter()
        .map(|measured_prefix| measured_prefix.string.as_str())
        .collect();

    assert_eq!(result_strings, vec!["success", "successive", "successor"]);
}

Notes

Autocompleter is currently a generic struct that limits the length of referenced strings to u8::MAX and maximum number of referenced strings to u32::MAX by default for space efficiency. A macro can be added later to instantiate it for other unsigned types.

Some of the tests require a file named words.txt file (highlighted link) in src/tests.

Citations

@article{10.14778/2977797.2977808,
author = {Deng, Dong and Li, Guoliang and Wen, He and Jagadish, H. V. and Feng, Jianhua},
title = {META: An Efficient Matching-Based Method for Error-Tolerant Autocompletion},
year = {2016},
issue_date = {June 2016},
publisher = {VLDB Endowment},
volume = {9},
number = {10},
issn = {2150-8097},
url = {https://doi.org/10.14778/2977797.2977808},
doi = {10.14778/2977797.2977808},
journal = {Proc. VLDB Endow.},
month = {jun},
pages = {828–839},
numpages = {12}
}

This paper is also available from the conference website here.

License

Dual-licensed under MIT and Apache-2.0. You may choose either license.

Contributions

Contributions to this project are likewise understood to be dual-licensed under MIT and Apache-2.0.