🦀 Rust crate that allows creating weighted prefix trees that can be used in autocomplete

Related tags

Learning Resources rust autocomplete trie prefix-tree autosuggestions weighted-trie
Overview

weighted_trie

🦀 Rust crate that allows creating weighted prefix trees that can be used in autocomplete

Released API Docs

License: Apache 2.0

Quickstart

To use weigthed-trie, add the following to your Cargo.toml file:

[dependencies]
weighted_trie = "0.1.0"  # NOTE: Replace to latest minor version.

Usage overview

use weighted_trie::WeightedTrie;

fn main() {
   let mut trie = WeightedTrie::new();
    // build trie with words and assoicated weights
    trie.insert("pie".to_owned(), 5);
    trie.insert("pita".to_owned(), 2);
    trie.insert("pi".to_owned(), 1);
    trie.insert("pizza".to_owned(), 10);

    // get prefix based suggestions sorted by weight
    let suggestions = trie.search("pi");
    assert_eq!(suggestions, vec!["pizza", "pie", "pita", "pi"]);

    let suggestions = trie.search("piz");
    assert_eq!(suggestions, vec!["pizza"]);

    // out of vocabulary
    let suggestions = trie.search("apple");
    assert_eq!(suggestions.len(), 0);

}

Alternatively you can use .build method

use weighted_trie::{WeightedString, WeightedTrie};

fn main() {
    let weighted_strings = vec![
           WeightedString {
               word: "pie".to_owned(),
               weight: 5,
           },
           WeightedString {
               word: "pita".to_owned(),
               weight: 2,
           },
           WeightedString {
               word: "pi".to_owned(),
               weight: 1,
           },
           WeightedString {
               word: "pizza".to_owned(),
               weight: 10,
           },
       ];

    let trie = WeightedTrie::build(weighted_strings);

}

Benchmarks

Using 100k weighted strings

weighted_trie/insert    time:   [342.41 ms 343.86 ms 345.56 ms]
weighted_trie/lookup    time:   [1.8608 ms 1.9351 ms 2.0834 ms]
weighted_trie/build     time:   [326.27 ms 330.74 ms 337.03 ms]

Guidelines

README.md is generated from cargo readme command. Do not manually update README.md instead edit src/lib.rs and then run cargo readme > README.md.

TODO:

  1. Add tests
  2. Benchmark lookup speed
  3. Benchmark insert speed
  4. Measure memory footprint
  5. Try low hanging fruit optimizations like usage of hashbrown instead of standart HashMap

License

License: Apache-2.0

You might also like...
:crab: Small exercises to get you used to reading and writing Rust code!
:crab: Small exercises to get you used to reading and writing Rust code!

rustlings 🦀 ❤️ Greetings and welcome to rustlings. This project contains small exercises to get you used to reading and writing Rust code. This inclu

The Rust Programming Language 33.1k Jan 2, 2023
This project contains small exercises to get you used to reading and writing Rust code
This project contains small exercises to get you used to reading and writing Rust code

rustlings 🦀 ❤️ Greetings and welcome to rustlings. This project contains small exercises to get you used to reading and writing Rust code. This inclu

Cynthia Tran 1 May 24, 2022
A set of Zero Knowledge modules, written in Rust and designed to be used in other system programming environments.

Zerokit A set of Zero Knowledge modules, written in Rust and designed to be used in other system programming environments. Initial scope Focus on RLN

vac 44 Dec 27, 2022
A relatively simple puzzle generator application written in Rust and used via Javascript
A relatively simple puzzle generator application written in Rust and used via Javascript

Puzzlip Basic Overview This is a relatively simple puzzle generator application written in Rust and used via Javascript in https://puzzlip.com. If you

Nenad 5 Dec 7, 2022
Elton is a benchmark utility written in rust aimed to be used to benchmark HTTP calls.

Elton Elton is an HTTP Benchmark utility with options to be used within an HTTP interface. Installation Elton is currently available via Docker or by

Emil Priver 5 Sep 22, 2023
An ownership model that is used to replace the Ring in Linux.

std-ownership An ownership model that is used to replace the Ring in Linux. It's 10x faster than Ring in Syscall. Overview The ownership system allows

Rhodes 4 Feb 13, 2023
TypeRust - simple Rust playground where you can build or run your Rust code and share it with others

Rust playground Welcome to TypeRust! This is a simple Rust playground where you can build or run your Rust code and share it with others. There are a

Kirill Vasiltsov 28 Dec 12, 2022
In this repository you can find modules with code and comments that explain rust syntax and all about Rust lang.
In this repository you can find modules with code and comments that explain rust syntax and all about Rust lang.

Learn Rust What is this? In this repository you can find modules with code and comments that explain rust syntax and all about Rust lang. This is usef

Domagoj Ratko 5 Nov 5, 2022
Charted's email service built in Rust that can be connected via gRPC

email-service is a small microservice to help transfer emails towards other people without trying to implement it in different languages. This is used in charted-server for member invitations, passwordless authentication, and more.

charted 7 Mar 6, 2023
Releases(v0.1.3)

  • v0.1.3(Feb 18, 2023)

    What's Changed

    • add build to WeightedTrie by @sa- in https://github.com/subpath/weighted_trie/pull/1

    New Contributors

    • @sa- made their first contribution in https://github.com/subpath/weighted_trie/pull/1

    Full Changelog: https://github.com/subpath/weighted_trie/compare/v0.1.2...v0.1.3

    Source code(tar.gz)
    Source code(zip)

  • v0.1.2(Feb 12, 2023)

  • v0.1.1(Feb 11, 2023)

  • v0.1.0(Feb 11, 2023)

Owner
Alexander Osipenko
Alexander Osipenko
GitHub
A pure-rust(with zero dependencies) fenwick tree, for the efficient computation of dynamic prefix sums.

indexset A pure-rust(with zero dependencies, no-std) fenwick tree, for the efficient computation of dynamic prefix sums. Background Did you ever have

Bruno Rucy Carneiro Alves de Lima 2 Jul 13, 2023
Rust 核心库和标准库的源码级中文翻译，可作为 IDE 工具的智能提示 (Rust core library and standard library translation. can be used as IntelliSense for IDE tools)

Rust 标准库中文版 这是翻译 Rust 库 的地方， 相关源代码来自于 https://github.com/rust-lang/rust。 如果您不会说英语，那么拥有使用中文的文档至关重要，即使您会说英语，使用母语也仍然能让您感到愉快。Rust 标准库是高质量的，不管是新手还是老手，都可以从中

wtklbm 493 Jan 4, 2023
A console viewer for trees – pet project to help me learn Rust.

treeviewer This is a pet project to help me learn Rust. But maybe it’ll end up being of actual use for someone? The idea is to write a program that, g

Daniel Janus 3 Jul 15, 2023
Core Temporal SDK that can be used as a base for language specific Temporal SDKs

Core SDK that can be used as a base for all other Temporal SDKs. Getting started See the Architecture doc for some high-level information. This repo u

temporal.io 136 Dec 21, 2022
This crate allows to generate a flat binary with the memory representation of an ELF.

flatelf Library This crate allows to generate a flat binary with the memory representation of an ELF. It also allows to generate a FLATELF with the fo

Roi Martin 3 Sep 29, 2022
A rust crate can find first `Err` in `Iterator>` and iterating continuously, without allocation.

Api Document first-err Find the first Err in Iterator<Result<T, E>> and allow iterating continuously. This crate is specifically designed to replace t

null 3 Oct 28, 2023
Intro: we are creating a software system for a pizza restaurant, one of the modules is supposed to handle the management of various pizza recipes and how the orders are put together, and a big part of the module will be the control of food types, the potential allergens in recipes, and calories counting.

rust_pizzeria Intro: we are creating a software system for a pizza restaurant, one of the modules is supposed to handle the management of various pizz

Flavio Rasseli 1 Oct 26, 2021
hashmap macro for creating hashmap from provided key/value pairs

HashMap Macro Creates a HashMap from provided key/value pairs. Usage use std::collections::HashMap; use hashmap_macro::hashmap; let m: HashMap<&str,

null 6 Oct 2, 2022
This is the Rust course used by the Android team at Google. It provides you the material to quickly teach Rust to everyone.

Comprehensive Rust ?? This repository has the source code for Comprehensive Rust ?? , a four day Rust course developed by the Android team. The course

Google 5.2k Jan 3, 2023
JackTheBox allows for client & server modifications to s&box independent of the current gamemode

JackTheBox allows for client & server modifications to s&box independent of the current gamemode (or even in the absence of a gamemode).

dank 5 Sep 27, 2022