Questions about different distance metrics on strings.
3
votes
1answer
59 views
Evaluation metric for an ordering algorithm
There is a sentence with N words.
The words are randomly shuffled.
I have a heuristic algorithm that tries to restore the original order.
I want to evaluate my algorithm on a dataset of several ...
3
votes
0answers
57 views
Distinguishing probabilistic, deterministic, and fuzzy matching methods
I have two datasets that I am trying to match to one another. One dataset's contents is a subset of the other, but contains typographical errors of varying types and magnitude.
I am applying the ...
6
votes
1answer
197 views
Alternative to Hamming distance for permutations
I have two strings, where one is a permutation of the other. I was wondering if there is an alternative to Hamming distance where instead of finding the minimum number of substitutions required, it ...
4
votes
2answers
327 views
Fast k mismatch string matching algorithm
I am looking for a fast k-mismatch string matching algorithm. Given a pattern string P of length m, and a text string T of length n, I need a fast (linear time) algorithm to find all positions where P ...
6
votes
1answer
119 views
Micro-optimisation for edit distance computation: is it valid?
On Wikipedia, an implementation for the bottom-up dynamic programming scheme for the edit distance is given. It does not follow the definition completely; inner cells are computed thus:
...
1
vote
1answer
157 views
Semantic clustering
I have a very specific question about semantic clustering.
I have a list of words/phrases. I want to run an intelligent semantic clustering algorithm on this list. Please let me know what the ...
7
votes
1answer
93 views
Determining how similar a given string is to a collection of strings
I'm not sure if this question belongs here and I apologize if not. What I am looking to do is to develop a programmatic way in which I can probabilistically determine whether a given string "belongs" ...
4
votes
1answer
91 views
Find string that minimizes the sum of the edit distances to all other strings in set
I have a set of strings $S$ and I am using the edit-distance (Levenshtein) to measure the distance between all pairs.
Is there an algorithm for finding the string $x$ which minimizes the sum of the ...
4
votes
2answers
282 views
Efficiently calculating minimum edit distance of a smaller string at each position in a larger one
Given two strings, $r$ and $s$, where $n = |r|$, $m = |s|$ and $m \ll n$, find the minimum edit distance between $s$ for each beginning position in $r$ efficiently.
That is, for each suffix of $r$ ...
3
votes
2answers
215 views
Turn one string into another with single letter substitions
I want to turn one string into another with only single letter substitions. What is a good way to do this, passing through only valid words in between (this website has some examples)?
Valid here ...
7
votes
2answers
205 views
How many strings are close to a given set of strings?
This question has been prompted by Efficient data structures for building a fast spell checker.
Given two strings $u,v$, we say they are $k$-close if their Damerau–Levenshtein distance¹ is small, ...
19
votes
3answers
881 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 ...
8
votes
1answer
193 views
Expressing an arbitrary permutation as a sequence of (insert, move, delete) operations
Suppose I have two strings. Call them $A$ and $B$. Neither string has any repeated characters.
How can I find the shortest sequence of insert, move, and delete operation that turns $A$ into $B$, ...
