Fuzzy Index for Python, written in Rust. Works like error-tolerant dict, keyed by a human input.

Related tags

Command-line fuzzdex
Overview

FuzzDex

FuzzDex is a fast Python library, written in Rust. It implements an in-memory fuzzy index that works like an error-tolerant dictionary keyed by a human input.

Algorithm

You load into fuzzdex series of short phrases - like street names consisting of one or multiple words, with an numerical index that identifies this street names in related dictionary of cities.

Then, you can query the index using a must-token (currently only one, but could be altered to use more) and additional should-tokens to read a total of limit of possibly matching phrases.

Must-token is trigramized (warszawa -> war ars rsz sza zaw awa) and all phrases containing given trigrams are initially read from the index. Trigrams have scores, the more common they are, the less they increase the phrase score. Trigrams of should-tokens additionally alter the score (positively when they match), but don't add additional phrases from index. Phrases are then sorted by score.

Top phrases are filtered to contain an optional constraint and the must-token with a maximal editing distance (Levenshtein) until limit of phrases is gathered.

Internally, the results of a must-token search are LRU cached as in practise it's pretty often repeated. Should-tokens vary and they are always recalculated.

Usecases

It was designed to match parts of a user supplied physical addresses to a data extracted from the OpenStreet map - in order to find streets and cities.

Address is first tokenized and then it's parts are matched against fuzzy dictionary of cities and streets. Additional constraints can limit the matched streets only to given city - or finding cities that have a given street.

Data is first searched for using trigrams (warszawa -> war ars rsz sza zaw awa), and then additionally filtered using maximal Levenshtein editing distance.

Original solution used fuzzy query of the Elasticsearch database, which worked - but was 21x slower in our tests.

Example

import fuzzdex
# Create two fuzzy indices with cities and streets.
cities = fuzzdex.FuzzDex()
# Warsaw has streets: Czerniakowska, Nowy Świat and Wawelska
cities.add_phrase("Warsaw", 1, constraints={1, 2, 3})
# Wrocław only Czerniawska
cities.add_phrase("Wrocław", 2, constraints={4})

streets = fuzzdex.FuzzDex()
# Streets with reversed constraints and own indices:
streets.add_phrase("Czerniakowska", 1, constraints={1})
streets.add_phrase("Nowy Świat", 2, constraints={1})
streets.add_phrase("Wawelska", 3, constraints={1})

streets.add_phrase("Czerniawska", 4, constraints={2})

# This recalculates trigram scores and makes index immutable:
cities.finish()
streets.finish()

# warszawa matches warsaw at editing distance 2.
cities.search("warszawa", [], max_distance=2, limit=60)
#    [{'origin': 'Warsaw', 'index': 1, 'token': 'warsaw',
#      'distance': 2, 'score': 200000.0, 'should_score': 0.0}]

# `świat` adds additional should score to the result and places it higher
# in case the limit is set:
streets.search("nowy", ["świat"], max_distance=2, constraint=1)
#    [{'origin': 'Nowy Świat', 'index': 2, 'token': 'nowy',
#      'distance': 0, 'score': 5.999, 'should_score': 7.4999}]

# Won't match with constraint 2.
streets.search("nowy", ["świat"], constraint=2)
#    []

# Quering for `czerniawska` will return `czerniakowska` (no constraints),
# but with a lower score and higher distance:
In [22]: streets.search("czerniawska", [], max_distance=2)
Out[22]:
#  [{'origin': 'Czerniawska', 'index': 4, 'token': 'czerniawska',
#   'distance': 0, 'score': 9.49995231628418, 'should_score': 0.0},
#  {'origin': 'Czerniakowska', 'index': 1, 'token': 'czerniakowska',
#   'distance': 2, 'score': 6.4999680519104, 'should_score': 0.0}]

Installation, development

You can install fuzzdex from PyPI when using one of the architectures it's published for (x86_64, few Python versions).

pip3 install fuzzdex

Or use maturin to build it locally:

pipenv install --dev
pipenv shell
maturin develop -r
pytest

You can also use cargo and copy or link the .so file directly (rename libfuzzdex.so to fuzzdex.so):

cargo build --release
ln -s target/release/libfuzzdex.so fuzzdex.so

build.sh has commands for building manylinux packages for PyPI.

You might also like...
A simple, modern fuzzy finder tool to run examples in a Cargo project.

cargo-rx cargo-rx is a simple, modern Runner for Examples in a Cargo project. This crate provides a single executable: rx. Basically anywhere you woul

Works out if this is running from inside a shell, and if so, which one.

pshell pshell answers the question "Is my application running in a shell, and if so, which one". Example: you are installing something and want to mak

A panic hook for wasm32-unknown-unknown that logs panics with console.error
A panic hook for wasm32-unknown-unknown that logs panics with console.error

console_error_panic_hook This crate lets you debug panics on wasm32-unknown-unknown by providing a panic hook that forwards panic messages to console.

Application microframework with command-line option parsing, configuration, error handling, logging, and shell interactions
Application microframework with command-line option parsing, configuration, error handling, logging, and shell interactions

Abscissa is a microframework for building Rust applications (either CLI tools or network/web services), aiming to provide a large number of features w

trigger io::Error's in test, and annotate their source

fault-injection docs Similar to the try! macro or ? operator, but externally controllable to inject faults during testing. Unlike the try! macro or ?

TUI input library supporting multiple backends
TUI input library supporting multiple backends

tui-input WARNING: Most of the functionality is only human tested. A TUI input library supporting multiple backends. This crate can be used with tui-r

Simple console input macros with the goal of being implemented in the standard library.

Simple console input macros with the goal of being implemented in the standard library.

Command line utility to remove duplicates from the given input.

Command line utility to remove duplicates from the given input. Note that huniq does not sort the input, it just removes duplicates.

omekasy is a command line application that converts alphanumeric characters in your input to various styles defined in Unicode.

omekasy is a command line application that converts alphanumeric characters in your input to various styles defined in Unicode. omekasy means "dress up" in Japanese.

Owner
Tomasz bla Fortuna
I do stuff. Mostly commercially recently, but still occasionally I waste time on small personal projects which made me who I am today.
Tomasz bla Fortuna
A library that creates a terminal-like window with feature-packed drawing of text and easy input handling. MIRROR.

BearLibTerminal provides a pseudoterminal window with a grid of character cells and a simple yet powerful API for flexible textual output and uncompli

Tommy Ettinger 43 Sep 10, 2022
This is choose, a human-friendly and fast alternative to cut and (sometimes) awk

Choose This is choose, a human-friendly and fast alternative to cut and (sometimes) awk Features terse field selection syntax similar to Python's list

Ryan Geary 1.3k Sep 21, 2022
Grep with human-friendly search output

hgrep: Human-friendly GREP hgrep is a grep tool to search files with given pattern and print the matched code snippets with human-friendly syntax high

Linda_pp 338 Sep 22, 2022
Codemod - Codemod is a tool/library to assist you with large-scale codebase refactors that can be partially automated but still require human oversight and occasional intervention

Codemod - Codemod is a tool/library to assist you with large-scale codebase refactors that can be partially automated but still require human oversight and occasional intervention. Codemod was developed at Facebook and released as open source.

Meta Archive 4k Sep 13, 2022
A simple, human-friendly, embeddable scripting language

Mica Language reference · Rust API A simple, human-friendly scripting language, developed one feature at a time. Human-friendly syntax inspired by Rub

Mica programming language 15 Sep 21, 2022
Rust Imaging Library's Python binding: A performant and high-level image processing library for Python written in Rust

ril-py Rust Imaging Library for Python: Python bindings for ril, a performant and high-level image processing library written in Rust. What's this? Th

Cryptex 5 Sep 12, 2022
Skim - Fuzzy Finder in rust!

Life is short, skim! Half of our life is spent on navigation: files, lines, commands… You need skim! It is a general fuzzy finder that saves you time.

Takayuki Maeda 0 May 16, 2021
Save cli commands and fuzzy find them later

crow - cli command memorizer What is crow? | Installation | Usage | FAQ What is crow? crow (command row) is a CLI tool to help you memorize CLI comman

sandstorm 7 Feb 17, 2022
Fzf - A command-line fuzzy finder

fzf is a general-purpose command-line fuzzy finder. It's an interactive Unix filter for command-line that can be used with any list; files, command hi

Junegunn Choi 47.2k Sep 26, 2022
🧠 A command-line utility for switching git branches more easily. Switch branches interactively or use a fuzzy search to find that long-forgotten branch name.

git-smart-checkout A git command extension for switching git branches more efficiently. About Interactively switch branches or fuzzy search for that f

Cezar Craciun 51 Sep 19, 2022