General Dev>In The News

Damn Cool Algorithms: Levenshtein Automata

CommunityNews

CommunityNews

Damn Cool Algorithms: Levenshtein Automata

In a previous Damn Cool Algorithms post, I talked about BK-trees, a clever indexing structure that makes it possible to search for fuzzy matches on a text string based on Levenshtein distance - or any other metric that obeys the triangle inequality. Today, I’m going to describe an alternative approach, which makes it possible to do fuzzy text search in a regular index: Levenshtein automata.

Read in full here:

http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levenshtein-Automata

This thread was posted by one of our members via one of our news source trackers.

View thread on forum
#algorithms
0 874 0

Where Next?

View thread on forum
algorithms
Home General Dev>In The News
#algorithms
0 874 0
Last post

Popular General Dev topics Top

First poster: mafinar
General Dev>In The News

F# Is The Best Programming Language Today
F# Is The Best Coding Language Today. If you want to personally pick up a programming language in order to become a better coder in what...
danielbmarkham.com
#f-sharp#programming
41 1882 14
New
First poster: AstonJ
General Dev>In The News

Wearable Microphone Jamming
We engineered a wearable microphone jammer that is capable of disabling microphones in its user’s surroundings, including hidden micropho...
sandlab.cs.uchicago.edu
/security
7 1834 3
New
First poster: bot
General Dev>In The News

Logitech Pop Keys review: Reliable wireless mechanical keyboard with a divisive style
Mediocre typing feel overshadows reliable wireless and fantastic battery life.
arstechnica.com
/keyboards#review
0 1557 0
New
CommunityNews
General Dev>In The News

Why study functional programming?
…or, “why make programming even harder?” Learning functional programming is an opportunity to discover a new way to represent programs, t...
acm.wustl.edu
#programming
4 1171 1
New
First poster: bot
General Dev>In The News

When Zig is safer and faster than Rust
When Zig is safer and faster than Rust. There are endless debates online about Rust vs. Zig, this post explores a side of the argument I...
zackoverflow.dev
/rust/zig
0 1459 0
New
CommunityNews
General Dev>In The News

The Definitive PHP 7.2, 7.3, 7.4, 8.0, and 8.1 Benchmarks (2023)
The Definitive PHP 7.2, 7.3, 7.4, 8.0, and 8.1 Benchmarks (2023). We tested the performance of 14 PHP platforms (WordPress, Drupal, Lara...
kinsta.com
/php
0 1888 0
New
CommunityNews
General Dev>In The News

Review of Linux on Minisforum V3 AMD Ryzen Tablet
A Brief Review of the Minisforum V3 AMD Tablet. Update: I have created an awesome-minisforum-v3 GitHub repository to list information fo...
mudkip.me
#linux#review#amd
0 4635 0
New
First poster: alvinkatojr
General Dev>In The News

The A.I. Monarchy
About accelerationism, NRx, and the intersection of technology, religion, and philosophy: an analysis of the essential ideas in the new A...
substack.com
2 871 1
New
CommunityNews
General Dev>In The News

GitSyncPad - Effortless Git Version Control
GitSyncPad is an innovative micro keypad designed for effortless Git version control. Execute commands like git add, git commit, and git ...
gitsyncpad.xyz
#git
0 616 0
New
CommunityNews
General Dev>In The News

Introducing Sidekiq 8.0
After six months of hard work, I’m thrilled to announce the general availability of Sidekiq 8.0! :partying_face::tada: Status Sidekiq is...
mikeperham.com
/ruby/rails
1 1368 0
New

Other popular topics Top

PragmaticBookshelf
General Dev>Learning Resources

Forge Your Future with Open Source
Free and open source software is the default choice for the technologies that run our world, and it’s built and maintained by people like...
pragprog.com
#pragprog#published-book/book-forge-your-future-with-open-source
3 5654 0
New
siddhant3030
General Dev>Dev Chat

Which vertical monitor do you use?
I’m thinking of buying a monitor that I can rotate to use as a vertical monitor? Also, I want to know if someone is using it for program...
#monitors#programming
51 4892 20
New
AstonJ
General Dev>Code Editors

Poll: Which code editor do you use?
You might be thinking we should just ask who’s not using VSCode :joy: however there are some new additions in the space that might give V...
#community#polls/vim/emacs#code-editors/vscode#notepad/sublime-text#atom/textmate#codespaces#brackets/onivim#geany
121 5796 61
New
AstonJ
General Dev>Hardware

BIIP MT3 Extended 2048 Custom Keycap Set (Drop)
This looks like a stunning keycap set :orange_heart: A LEGENDARY KEYBOARD LIVES ON When you bought an Apple Macintosh computer in the e...
/keyboards#apple#keycaps#mechanical-keyboards
14 6713 7
New
Exadra37
Linux>Chat

RancherOS is in end of life
Oh just spent so much time on this to discover now that RancherOS is in end of life but Rancher is refusing to mark the Github repo as su...
#linux#rancheros
10 6358 6
New
foxtrottwist
General Dev>Dev Chat

Warp—The blazingly fast, Rust-based terminal
A few weeks ago I started using Warp a terminal written in rust. Though in it’s current state of development there are a few caveats (tab...
/rust#terminal
52 6785 22
New
AstonJ
Science/Tech>Health & Diet

David Sinclair's new Lifespan podcast
We’ve talked about his book briefly here but it is quickly becoming obsolete - so he’s decided to create a series of 7 podcasts, the firs...
#health#podcasts#bio-hackers#david-sinclair
87 6790 49
New
PragmaticBookshelf
Community>In The Spotlight

Spotlight: Erin Dees (Author) Interview and AMA!
Author Spotlight Erin Dees @undees Welcome to our new author spotlight! We had the pleasure of chatting with Erin Dees, co-author of ...
#author-spotlight/ruby/rails/book-effective-testing-with-rspec-3/book-seven-more-languages-in-seven-weeks/book-cucumber-recipes#rspec
24 4247 11
New
First poster: AstonJ
General Dev>In The News

Jan: An open source alternative to ChatGPT that runs on the desktop
Jan | Rethink the Computer. Jan turns your computer into an AI machine by running LLMs locally on your computer. It’s a privacy-focus, l...
jan.ai
#desktop#chatgpt
4 5652 4
New
NewsBot
Backend>Official News

Node.js v22.14.0 released!
Node.js v22.14.0 has been released. Link: Release 2025-02-11, Version 22.14.0 'Jod' (LTS), @aduh95 · nodejs/node · GitHub
github.com
/nodejs#official-news
0 4251 0
New
Back to top

Sponsor Spotlight

coders51

We build reliable cloud platforms for business-critical systems.

General Dev>In The News

General Dev In The News ❯

Latest on Devtalk

Devtalk ❯

We ❤️ helpful members!

We reward our most helpful members via our MOTM scheme - by giving away a whopping 25 books per year!

Member of the Month

Devtalk Sponsors

Pragmatic Bookshelf

Practical resources that improve the lives of professional developers.

Erlang Solutions

We build trusted fault-tolerant systems that scale to billions of users.

Honeybadger

Real-time error tracking, performance insights, and observability for devs.

EEF

Supporting innovation across the BEAM ecosystem.

coders51

We build reliable cloud platforms for business-critical systems.

Manning Publications

Develop your skills with books, videos, and courses.

AppSignal

Catch errors, track performance, monitor hosts and more.

WyeWorks

Enabling companies to succeed by building software people love.

Pragmatic Studio

Courses that move you from confusion to "Aha, now I get it!"

View all our sponsors ❯

Categories:

Sub Categories:

Popular Portals

Devtalk Sponsors

Pragmatic Bookshelf

Practical resources that improve the lives of professional developers.

Erlang Solutions

We build trusted fault-tolerant systems that scale to billions of users.

Honeybadger

Real-time error tracking, performance insights, and observability for devs.

EEF

Supporting innovation across the BEAM ecosystem.

coders51

We build reliable cloud platforms for business-critical systems.

Manning Publications

Develop your skills with books, videos, and courses.

AppSignal

Catch errors, track performance, monitor hosts and more.

WyeWorks

Enabling companies to succeed by building software people love.

Pragmatic Studio

Courses that move you from confusion to "Aha, now I get it!"

View all our sponsors ❯

We're in Beta

About us Mission Statement See our Roadmap