Fast approximate string matching with large edit distances in Big Data (2015)

Image for post
Image for post
Source: https://www.flickr.com/photos/theredproject/3968278028

1 million times faster spelling correction for edit distance 3

Billion times faster approximate string matching for edit distance >4

Application fields

Edit distance metrics

Benchmark

Image for post
Image for post

Dictionary corpus

Speed gain

Computational complexity

Precalculation cost

Image for post
Image for post
Image for post
Image for post

Source code

Comparison to other approaches and common misconceptions

Correction vs. Completion

Written by

Founder SeekStorm (Search-as-a-Service), FAROO (P2P Search) https://seekstorm.com https://github.com/wolfgarbe https://www.quora.com/profile/Wolf-Garbe

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store