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

Remote working: Is Big Tech going off work from home?
On Wednesday last week, Google’s Fiona Cicconi wrote to company employees. She announced that Google was bringing forward its timetable ...
bbc.co.uk
#remote
31 1479 10
New
First poster: dyowee
General Dev>In The News

There’s No Such Thing as Clean Code
Everyone seems to be striving for ‘clean’ code at the moment. You can’t read a blog post without the author telling you how clean their a...
steveonstuff.com
#code
31 1701 9
New
First poster: joeb
General Dev>In The News

Safari now supports File System Access API with private origin
The File System Access API with Origin Private File System. WebKit supports new API that makes it possible for web apps to create, open,...
webkit.org
#api#safari
43 3791 21
New
First poster: bot
General Dev>In The News

I made a home security system, powered by a Raspberry Pi 3
Raspberry Pi security alarm — the basics. In November last year — I started building a DIY security alarm system, using a Raspberry Pi a...
blog.cavelab.dev
/security
0 2261 0
New
First poster: bot
General Dev>In The News

ChatML: ChatGPT API expects a structured format, called Chat Markup Language
openai-python/chatml.md at main · openai/openai-python. The OpenAI Python library provides convenient access to the OpenAI API from appl...
github.com
#chat#api#chatgpt
0 1472 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 1459 0
New
First poster: bot
General Dev>In The News

ONNX Runtime merges WebGPU backend
[js/web] WebGPU backend via JSEP by fs-eire · Pull Request #14579 · microsoft/onnxruntime. Description This change introduced the follo...
github.com
#backend
0 1372 0
New
CommunityNews
General Dev>In The News

Deepseek - starting this week we'll open-source 5 repos
We’re a tiny team @deepseek-ai pushing our limits in AGI exploration. Starting this week , Feb 24, 2025 we’ll open-source 5 repos – one ...
github.com
#github/deepseek
1 1227 0
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 1056 2
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

Other popular topics Top

ohm
Science/Tech>Tech Chat

Games! Which do you play?
Which, if any, games do you play? On what platform? I just bought (and completed) Minecraft Dungeons for my Nintendo Switch. Other than ...
#games
246 6097 101
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 9886 77
New
AstonJ
General Dev>Hardware

Poll: Which keyboard layout do you use?
poll poll Be sure to check out @Dusty’s article posted here: An Introduction to Alternative Keyboard Layouts It’s one of the best write-...
colemakmods.github.io
#polls/keyboards
10 6048 11
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
AstonJ
General Dev>Dev Chat

Languages Without Garbage Collection
Continuing the discussion from Thinking about learning Crystal, let’s discuss - I was wondering which languages don’t GC - maybe we can c...
#garbage-collection
21 5575 7
New
Margaret
General Dev>Sales

Get 50% off these PragProg books during our Think Again Sale
Think Again 50% Off Sale » The theme of this sale is new perspectives on familiar topics. Enter coupon code ThinkAgain2021 at checkout t...
#community#pragprog/elixir/book-a-common-sense-guide-to-data-structures-and-algorithms-second-edition/book-programming-machine-learning/book-the-ray-tracer-challenge/book-forge-your-future-with-open-source/book-software-design-x-rays#algorithms/book-testing-elixir#machine-learning#sale/book-concurrent-data-processing-in-elixir/book-intuitive-python
8 6415 2
New
AstonJ
Data Science

Can AI/ML predict a lottery win?
Biggest jackpot ever apparently! :upside_down_face: I don’t (usually) gamble/play the lottery, but working on a program to predict the...
#ai#machine-learning
19 3939 10
New
Maartz
General Dev>Dev Chat

Roc Language - a new purely functional programming language built for speed and ergonomics
Hi folks, I don’t know if I saw this here but, here’s a new programming language, called Roc Reminds me a bit of Elm and thus Haskell. ...
#programminguages#functional-programming
49 5164 14
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 8550 13
New
PragmaticBookshelf
Backend>Learning Resources

Ash Framework
Explore the power of Ash Framework by modeling and building the domain for a real-world web application. Rebecca Le @sevenseacat and ...
pragprog.com
#pragprog/elixir#published-book/ash/book-ash-framework
15 7555 9
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