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

Where Next?

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

Popular General Dev topics Top

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 1842 6
New
First poster: cpgo
General Dev>In The News

8 Reasons to ditch Chrome and use Firefox
8 reasons to ditch Chrome and switch to Firefox. Chrome may dominate, but Firefox is a known name among browsers for a reason. Whether y...
pcworld.com
#chrome#firefox
73 1702 41
New
First poster: bot
General Dev>In The News

Introducing the ChatGPT/LLM error tracker
Large Language Models like ChatGPT say The Darnedest Things. The Errors They MakeWhy We Need to Document Them, and What We Have Decided ...
garymarcus.substack.com
#error#chatgpt
0 3161 0
New
First poster: bot
General Dev>In The News

Fish shell to be rewritten in Rust
Rewrite it in Rust by ridiculousfish · Pull Request #9512 · fish-shell/fish-shell. (Sorry for the meme; also this is obligatory.) I thi...
github.com
/rust#shell#fish
0 1226 0
New
First poster: bot
General Dev>In The News

Jailbreak Chat: A collection of ChatGPT jailbreaks
Jailbreak Chat. Collection of ChatGPT jailbreak prompts
jailbreakchat.com
#chat#chatgpt
0 1415 0
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 1255 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 1262 0
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 347 5
New
CommunityNews
General Dev>In The News

Self-Hosting a Firefox Sync Server
After switching from Firefox to LibreWolf, I became interested in the idea of self-hosting my own Firefox Sync server. Although I had see...
blog.diego.dev
#hosting#firefox
0 559 0
New
First poster: alvinkatojr
General Dev>In The News

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

Other popular topics Top

AstonJ
General Dev>Dev Chat

Best chairs for developers?
What chair do you have while working… and why? Is there a ‘best’ type of chair or working position for developers?
#workspace#opinions
74 5139 41
New
dasdom
General Dev>Dev Chat

Standing Desks
No chair. I have a standing desk. This post was split into a dedicated thread from our thread about chairs :slight_smile:
#workspace#opinions
177 8971 77
New
PragmaticBookshelf
Backend>Learning Resources

Concurrent Data Processing in Elixir
Learn different ways of writing concurrent code in Elixir and increase your application's performance, without sacrificing scalability or...
pragprog.com
#pragprog/elixir#published-book/book-concurrent-data-processing-in-elixir
78 4938 24
New
gagan7995
Backend>Questions

Please tell me how to write a query for this in nodejs
API 4 Path: /user/following/ Method: GET Description: Returns the list of all names of people whom the user follows Response [ { ...
/nodejs
7 3234 3
New
PragmaticBookshelf
Backend>Learning Resources

Effective Haskell
Build efficient applications that exploit the unique benefits of a pure functional language, learning from an engineer who uses Haskell t...
pragprog.com
#pragprog/haskell#published-book/book-effective-haskell
15 6980 1
New
PragmaticBookshelf
Backend>Learning Resources

Programming Ruby 3.2 (5th Edition)
Programming Ruby is the most complete book on Ruby, covering both the language itself and the standard library as well as commonly used t...
twitter.com
#pragprog/ruby/rails#published-book/book-programming-ruby-3-2-5th-edition
28 5151 13
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 3246 9
New
PragmaticBookshelf
Community>In The Spotlight

Spotlight: Tammy Coron (Author) Interview and AMA!
Author Spotlight: Tammy Coron @Paradox927 Gaming, and writing games in particular, is about passion, vision, experience, and immersio...
/swift/book-apple-game-frameworks-and-technologies
36 3796 18
New
PragmaticBookshelf
Community>In The Spotlight

Spotlight: Peter Ullrich (Author) Interview and AMA!
Author Spotlight: Peter Ullrich @PJUllrich Data is at the core of every business, but it is useless if nobody can access and analyze ...
/elixir/phoenix/book-building-table-views-with-phoenix-liveview
72 4178 21
New
AstonJ
AI>Chat

Post your DeepSeek results
Curious what kind of results others are getting, I think actually prefer the 7B model to the 32B model, not only is it faster but the qua...
/deepseek
15 2236 15
New
Back to top

Sponsor Spotlight

Manning

Develop your skills with books, videos, and courses.

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