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

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 868 0
New
First poster: andrea
General Dev>In The News

Why interruptions are frustrating to developers
What’s the real cost of interruptions? I illustrate all the context developers keep in their head and how it starts to decay immediately ...
tellspin.app
11 971 4
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 1250 3
New
CommunityNews
General Dev>In The News

LiveKit – open-source, high performance WebRTC infrastructure
GitHub - livekit/livekit: Scalable, high-performance WebRTC SFU. SDKs in JavaScript, React, React Native, Flutter, Swift, Kotlin, Unity/C...
github.com
#infrastructure#performance#webrtc
1 1103 1
New
CommunityNews
General Dev>In The News

How to design a good API and why it matters (2006)
ABSTRACT In lieu of a traditional , I’ve tried to distill the essence of the talk into a collection of maxims: All programmers are API ...
dl.acm.org
#api#design
2 923 1
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 969 0
New
First poster: joeb
General Dev>In The News

50 Shades of Go
50 Shades of Go: Traps, Gotchas, and Common Mistakes for New Golang Devs. Go is a simple and fun language, but, like any other language,...
devs.cloudimmunity.com
/go
1 762 1
New
First poster: dyowee
General Dev>In The News

Rust: The wrong people are resigning
Rust: The wrong people are resigning. Rust: The wrong people are resigning. GitHub Gist: instantly share code, notes, and snippets.
gist.github.com
/rust
4 843 6
New
First poster: joeb
General Dev>In The News

Rust has been forked to the Crab Language
GitHub - crablang/crab: A community fork of a language named after a plant fungus. All of the memory-safe features you love, now with 100...
github.com
/rust
0 843 1
New
First poster: dyowee
General Dev>In The News

Go Package for Building Progressive Web Apps
A Go package for building Progressive Web Apps. A package for building progressive web apps (PWA) with the Go programming language (Gola...
go-app.dev
#apps/go#web/wasm
2 753 1
New

Other popular topics Top

PragmaticBookshelf
Community>In The Spotlight

Spotlight: Brian P. Hogan (Author)
A PragProg Hero’s Journey with Brian P. Hogan @bphogan Have you ever worried that your only legacy will be in the form of legacy...
#pragprog#author-spotlight
50 3317 20
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 4182 20
New
Rainer
Community>Journals

Programming Erlang Book Club
My first contact with Erlang was about 2 years ago when I used RabbitMQ, which is written in Erlang, for my job. This made me curious and...
/erlang/book-programming-erlang-2nd-edition#book-club
195 6291 95
New
AstonJ
General Dev>Hardware

Planck vs Preonic vs Subatomic (Keyboards)
I ended up cancelling my Moonlander order as I think it’s just going to be a bit too bulky for me. I think the Planck and the Preonic (o...
/keyboards#mechanical-keyboards#ortholinear#planck#preonic
105 14240 47
New
Exadra37
Linux>Questions

What is the most minimalist Linux server distro?
I am asking for any distro that only has the bare-bones to be able to get a shell in the server and then just install the packages as we ...
#linux#servers
66 21193 24
New
AstonJ
Backend>Chat

How to install Ruby 3 with ASDF
In case anyone else is wondering why Ruby 3 doesn’t show when you do asdf list-all ruby :man_facepalming: do this first: asdf plugin-upd...
/ruby#asdf
11 5228 4
New
PragmaticBookshelf
Backend>Learning Resources

Programming Phoenix LiveView
Build highly interactive applications without ever leaving Elixir, the way the experts do. Let LiveView take care of performance, scalabi...
pragprog.com
#pragprog/elixir/phoenix#published-book/book-programming-phoenix-liveview
61 3311 14
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 2926 3
New
mafinar
Backend>Chat

Data Structures and Algorithms with Elixir
This is going to be a long an frequently posted thread. While talking to a friend of mine who has taken data structure and algorithm cou...
/elixir#algorithms#data-structures
108 8977 31
New
Help
Game Dev>Questions

Can I use Java to program a game for Nintendo switch?
I am trying to crate a game for the Nintendo switch, I wanted to use Java as I am comfortable with that programming language. Can you use...
/java#nintendo
8 3335 3
New
Back to top

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