Linked Questions

1 vote
0 answers
85 views

How to find close match of levenshtein distance [duplicate]

Let's say we have some function, float distance(String a, String b) { /*...*/ } to find the Levenshtein distance between two strings, and we have a large array ...
Joseph Nields's user avatar
43 votes
2 answers
9k views

Efficient data structures for building a fast spell checker

I'm trying to write a spell-checker which should work with a pretty large dictionary. I really want an efficient way to index my dictionary data to be used using a Damerau-Levenshtein distance to ...
Charles Menguy's user avatar
3 votes
2 answers
8k views

What is an efficient data structure for prefix matching?

I'm looking for an data structure that supports efficient random prefix matching queries (pattern) over a previously known set of words (dictionary). The dictionary is expected to contain about 10,000 ...
Abhijit Sarkar's user avatar
5 votes
2 answers
2k views

How fast can we identifiy almost-duplicates in a list of strings?

I'm having trouble figuring out the upper bound running time for this scenario: Input: $N$ number of strings $M$ upper bound of string length $T$ threshold for edit distance (2 strings with a ...
Eran Medan's user avatar
6 votes
1 answer
1k views

How to compare/cluster millions of strings?

I have around 1,000,000 of strings of variable length (from 200 to 50000) that can contain 5 characters (A, B, C, D, E). What I actually want is to cluster them together if they are similar enough. ...
Ivan's user avatar
  • 273
0 votes
1 answer
2k views

Large-scale string clustering

I've more than 10 million strings of length 1-100 characters. This number will be even bigger in the future. I'm interested in clustering this data, but I'm not quite sure what would be effective at ...
James Smith's user avatar
2 votes
0 answers
645 views

Matching strings in one set to strings in another based on Levenshtein distance

Suppose I have two sets, A and B, which each have one or more strings. I'm looking for an algorithm that'll go through each ...
Bilal Akil's user avatar
2 votes
1 answer
147 views

Approximate Similarity Search

I am implementing an approximate similarity search using multi-index hashing. I have a set (T) of millions of strings (of same length) and I have a query string(P) (or set of strings) that needs to ...
viz12's user avatar
  • 23
1 vote
2 answers
63 views

Title matching against human input

I am attempting to match human input of titles to a list of titles, and also show likely candidates when a human enters a title not known. Ideally I'd also have some way to suggest the human input of ...
Anon Coward's user avatar
0 votes
1 answer
59 views

How to check rapidly if an element is present in a large set of data

I am trying to harvest scientific publications data from different online sources like Core, PMC, arXiv etc. From these sources I keep the metadata of the articles (title, authors, abstract etc.) and ...
Agelos's user avatar
  • 103