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 660 0

Where Next?

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

Popular General Dev topics Top

First poster: bot
General Dev>In The News

20 patterns to watch for in your engineering team (pdf)
A field guide to help you recognize achievement, spot A field guide to help you recognize achievement, spot bottlenecks, and debug your d...
pluralsight.com
0 986 0
New
First poster: Maartz
General Dev>In The News

Keyboard lets people type so fast it’s banned from typing competitions
This Keyboard Lets People Type So Fast It’s Banned From Typing Competitions. A new peripheral lets you keep typing without ever lifting ...
vice.com
#typing#type#keyboard
13 1663 6
New
OvermindDL1
General Dev>In The News

Helix, a Kakoune inspired Vim-model text editor (written in Rust)
Yet another rust-made text editor, though I’m really liking the looks of how this one works!
/rust
5 2078 1
New
First poster: bot
General Dev>In The News

The overengineered Solution to my Pigeon Problem
The overengineered Solution to my Pigeon Problem. TL;DR: I built a wifi-equipped water gun to shoot the pigeons on my balcony, controlle...
maxnagy.com
0 4367 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 1299 0
New
CommunityNews
General Dev>In The News

Apple Patents Suggest Future AirPods Could Monitor Biosignals and Brain Activity
Apple Patents Suggest Future AirPods Could Monitor Biosignals & Brain Activity - AppleMagazine. The US Patent & Trademark Office...
applemagazine.com
#apple#monitor
0 1041 0
New
First poster: joni
General Dev>In The News

My experience trying to write human-sounding articles using Claude AI
My experience trying to write original, full-length human-sounding articles using Claude AI. You can use AI tools like Claude to help yo...
idratherbewriting.com
0 1010 1
New
First poster: dyowee
General Dev>In The News

Software engineering job openings hit five-year low?
Software engineering job openings hit five-year low?. There are 35% fewer software developer job listings on Indeed today, than five yea...
blog.pragmaticengineer.com
#job
5 321 2
New
First poster: AstonJ
General Dev>In The News

On the benefits of learning in public
On the benefits of learning in public. Learning in public helps me grow as an engineer and seems to benefit others too. Here’s why I sho...
gilesthomas.com
#learning
6 220 5
New
First poster: alvinkatojr
General Dev>In The News

Yoke is really cool
Infrastructure as code, but actually
xeiaso.net
2 73 1
New

Other popular topics Top

AstonJ
General Dev>Dev Chat

Which language or framework do you want to learn next?
Curious to know which languages and frameworks you’re all thinking about learning next :upside_down_face: Perhaps if there’s enough peop...
#community#learning
243 5922 95
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 6073 7
New
AstonJ
General Dev>Dev Chat

How fast do you type? Check your WPM here!
Do the test and post your score :nerd_face: :keyboard: If possible, please add info such as the keyboard you’re using, the layout (Qw...
typing-speed-test.aoeu.eu
/keyboards
82 6920 31
New
PragmaticBookshelf
Community>In The Spotlight

Spotlight: Paolo Perrotta (Author)
“A Mystical Experience” Hero’s Journey with Paolo Perrotta @nusco Ever wonder how authoring books compares to writing articles?...
#community#author-spotlight/book-programming-machine-learning/book-metaprogramming-ruby-2
31 3538 15
New
PragmaticBookshelf
Community>In The Spotlight

Spotlight: James Stanier (Author) Interview and AMA!
Author Spotlight James Stanier @jstanier James Stanier, author of Effective Remote Work , discusses how to rethink the office as we e...
#pragprog#remote/book-effective-remote-work
29 4082 12
New
AstonJ
General Dev>Code Editors

Doom-Emacs: Can't find emacs in your PATH
If you get Can't find emacs in your PATH when trying to install Doom Emacs on your Mac you… just… need to install Emacs first! :lol: bre...
#macos/emacs#doom-emacs
4 4891 0
New
PragmaticBookshelf
Community>In The Spotlight

Spotlight: Mike Riley (Author) Interview and AMA!
Author Spotlight Mike Riley @mriley This month, we turn the spotlight on Mike Riley, author of Portable Python Projects. Mike’s book ...
#author-spotlight/python#iot/book-portable-python-projects#internet-of-things
62 6351 19
New
DevotionGeo
General Dev>Questions

Do you prefer regular mechanical keyboards or low profile mechanical keyboards and why?
I have always used antique keyboards like Cherry MX 1800 or Cherry MX 8100 and almost always have modified the switches in some way, like...
/keyboards#mechanical-keyboards
27 2843 9
New
PragmaticBookshelf
Backend>Learning Resources

Engineering Elixir Applications
Develop, deploy, and debug BEAM applications using BEAMOps: a new paradigm that focuses on scalability, fault tolerance, and owning each ...
pragprog.com
#pragprog/elixir#published-book/book-engineering-elixir-applications
40 2292 21
New
AstonJ
Backend>Questions

Psql: error: connection to server on socket "/tmp/.s.PGSQL.5432" failed: No such file or directory
If you’re getting errors like this: psql: error: connection to server on socket “/tmp/.s.PGSQL.5432” failed: No such file or directory ...
#macos/rails/postgresql
1 2188 1
New
Back to top

Sponsor Spotlight

Erlang Solutions

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

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.

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'll 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.

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'll 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