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: bot
General Dev>In The News

Neovim nightly, v0.5.0 and v0.4.4 released!
Neovim nightly, v0.5.0 and v0.4.4 has been released. Link: Release Nvim development (prerelease) build · neovim/neovim · GitHub Link:...
github.com
#official-news/neovim
0 1719 0
New
First poster: bot
General Dev>In The News

Kyria Build, Part 1: A wireless ergonomic keyboard
It has some interesting features: It’s entirely wireless (the left half speaks Bluetooth to the right half, and the right half speaks B...
ianthehenry.com
#ergonomic#keyboard
0 1719 0
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 1773 1
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
CommunityNews
General Dev>In The News

Building GitHub with Ruby on Rails
Building GitHub with Ruby and Rails | The GitHub Blog. Since the beginning, GitHub.com has been a Ruby on Rails monolith. Today, the app...
github.blog
/ruby/rails#github
1 1159 1
New
First poster: FatimaAdamu
General Dev>In The News

Two US lawyers fined for submitting fake court citations from ChatGPT
Two US lawyers fined for submitting fake court citations from ChatGPT. Law firm also penalised after chatbot invented six legal cases th...
theguardian.com
#chatgpt
0 2231 3
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 1283 1
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 1154 0
New
First poster: alvinkatojr
General Dev>In The News

Knowing CSS is mastery to Front end Development
There are countless articles why developers should not focus on Frameworks too much and instead learn to understand the underlying langua...
helloanselm.com
#css#development
2 745 1
New
CommunityNews
General Dev>In The News

TrueSkill 2: An improved Bayesian skill rating system - Microsoft Research
Online multiplayer games, such as Gears of War and Halo, use skill-based matchmaking to give players fair and enjoyable matches. They dep...
microsoft.com
#microsoft
0 1031 0
New

Other popular topics Top

PragmaticBookshelf
Hybrid>Learning Resources

Programming Flutter
Instantly view the changes you make to an app with stateful hot reload, and define a declarative UI in the same language as the app logic...
pragprog.com
#pragprog/book-programming-flutter#published-book/flutter
11 4501 1
New
PragmaticBookshelf
General Dev>Learning Resources

Seven More Languages in Seven Weeks
Learn from the award-winning programming series that inspired the Elixir language, and go on a step-by-step journey through the most impo...
pragprog.com
#pragprog/elixir/julia/lua#published-book#factor/elm#minikanren/idris/book-seven-more-languages-in-seven-weeks
4 5862 0
New
Exadra37
Linux>Questions

AMD or Intel for Programming with Linux as the OS?
I am thinking in building or buy a desktop computer for programing, both professionally and on my free time, and my choice of OS is Linux...
#mobile#android#web-development#linux#desktop-computer#mobile-development
36 6006 10
New
PragmaticBookshelf
Game Dev>Learning Resources

Hands-on Rust: Effective Learning through 2D Game Development and Play
Rust is an exciting new programming language combining the power of C with memory safety, fearless concurrency, and productivity boosters...
pragprog.com
#pragprog/rust#published-book/book-hands-on-rust
117 10879 30
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 5961 4
New
sir.laksmana_wenk
Game Dev>Questions

I want to learn how make a game, but where should I start?
I’m able to do the “artistic” part of game-development; character designing/modeling, music, environment modeling, etc. However, I don’t...
#game-dev
15 4965 9
New
AnfaengerAlex
Android>Questions

Unresolved Reference to android in build.gradle.kts – Beginner Issue
Hello, I’m a beginner in Android development and I’m facing an issue with my project setup. In my build.gradle.kts file, I have the foll...
#binding
0 7460 2
New
PragmaticBookshelf
Backend>Learning Resources

MySQL 9 Essentials
A concise guide to MySQL 9 database administration, covering fundamental concepts, techniques, and best practices. Neil Smyth MySQL...
pragprog.com
#pragprog#published-book/mysql/book-mysql-9-essentials
2 4162 0
New
PragmaticBookshelf
Backend>Learning Resources

Kotlin Coroutine Confidence
Escape callback hell and ship fast, clean code that reads as smoothly as it runs. Squash bugs and stamp out memory leaks with an intuitiv...
pragprog.com
#pragprog/java/kotlin#published-book/book-kotlin-coroutine-confidence
14 3688 10
New
PragmaticBookshelf
Backend>Learning Resources

Advanced Functional Programming with Elixir
Use advanced functional programming principles, practical Domain-Driven Design techniques, and production-ready Elixir code to build scal...
joekoski.com
#pragprog/elixir#published-book#functional-programming/book-advanced-functional-programming-with-elixir
43 4989 22
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!"

Linux New Media

Publishing Linux Magazine, ADMIN, and MakerSpace for 25+ years.

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

Linux New Media

Publishing Linux Magazine, ADMIN, and MakerSpace for 25+ years.

View all our sponsors ❯

We're in Beta

About us Mission Statement See our Roadmap