ashvardanian / ashvardanian/StringZilla

Levenstein automata for even moar perf?

Open
#243 1 comment 0 reactions 0 assignees View on GitHub
core enhancement performance
Dominant language
C
Stars
3.6k
Forks
135
PR merge metrics
No merged PRs in 30d

Description

### Describe what you are looking for

Noob question: would a levenstein automata in stringzilla allow for even faster fuzzy search?
https://blog.mikemccandless.com/2011/03/lucenes-fuzzyquery-is-100-times-faster.html?m=1
There is also https://arxiv.org/abs/1008.1191

### Can you contribute to the implementation?

- [ ] I can contribute

### Is your feature request specific to a certain interface?

It applies to everything

### Contact Details

_No response_

### Is there an existing issue for this?

- [x] I have searched the existing issues

### Code of Conduct

- [x] I agree to follow this project's Code of Conduct

Contributor guide

Open the contributing guide

Research direction

Start by reviewing the linked Lucene article and arXiv paper, then compare their approach with StringZilla's existing edit-distance and search capabilities. A concrete follow-up would need to define the affected interfaces, benchmark target, and acceptance criteria; the issue currently names none.

Written by the indexing model from the issue text.

Assessment

Tech stack
c
Domain
performance, search
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.