Linked Questions
10 questions linked to/from Efficient map data structure supporting approximate lookup
1
vote
0
answers
83
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 ...
- 121
43
votes
2
answers
8k
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 ...
- 1,173
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 ...
- 283
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 ...
- 431
6
votes
1
answer
996
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. ...
- 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 ...
2
votes
0
answers
612
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 ...
- 121
2
votes
1
answer
131
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 ...
- 23
1
vote
2
answers
61
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 ...
- 111
0
votes
1
answer
54
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 ...
- 103