Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

# Questions tagged [string-metrics]

Questions about different distance metrics on strings.

53 questions
Filter by
Sorted by
Tagged with
43 views

### Edit distance between all word pairs

Let there be a dictionary of M words with average length N. We want to compute an M×M matrix of edit distances between all word pairs. Since there are M² word pairs, and the pairwise edit distance ...
30 views

### Can we compute edit distance in strongly sub-quadratic time?

Can we compute the edit distance between two strings of length $n$ in strongly sub-quadratic time, i.e., in time $O(n^{2−\epsilon})$ for some $\epsilon>0$?
37 views

### Sort by typical position?

Lets say, we have a lot of lists (sequences of variable length) of some limited set of elements: ...
39 views

### Is there a heuristic or function to determine if two arrays of integers are alike or similar

What I am trying to do is determine "closeness" or how similar are arrays of integers (or byte arrays, doesn't matter). For example, let's say a = [0, 1, 2, 3, 4], <...
14 views

### List of metrics for dates

I am given a set of pairs of dates and would like to extract features I can put into an machine learning algorithm. Thus far I have already written two different metrics, however I didn't find much ...
46 views

### Map a set of strings to another set of strings, optimise similarity

Suppose we have a similarity measure s : String x String -> [0, 1] and sets K, L in ...
187 views

### Complexity of Block edit distance with Swapping only

Suppose I have distinct letters in an alphabet $\sum = \{a_1,a_2,...,a_n\}$. I also have two permutations of these letters, let's call them $A,B$. How can I find the Edit distance between $A$ and $B$ ...
85 views

### What is the error when using Levenshtein distance on flattened binary trees?

I need to calculate the edit distance between many pairs of binary trees. Unfortunately this is computationally expensive. The trees are stored as a flattened list of indices into node and terminal ...
199 views

### similarity between strings

I have found this tool: https://www.tools4noobs.com/online_tools/string_similarity/ and it says that is based on the article: "An O(ND) Difference Algorithm and its Variations" available on: http:/...
337 views

### Are two strings equal if all deciders for a language take the same amount of time for both?

Let $X_*^L$ be the set of all deterministic Turing machines $M$ which decide the language $L$ and have the property: $\forall x,y \in \Sigma^*: t_M(xy) \ge t_M(x) + t_M(y)$ (**) where $t_M(w)$ is ...
145 views

135 views

### String distance metric for possibly truncated words

I am looking for the optimal string distance metric to indicate similarity/difference between possibly truncated words. For example, I would like to find the distance metric between the name "Richard" ...
970 views

### How to do high performance string matching when comparing unordered sets of tokens [closed]

This is the problem: I have some strings stored in the database. Each of the strings can be seen as a set of tokens separated by comma with no repetition (I mean a token cannot appear more than one ...
86 views

### What is MongeElkan distance between words? [duplicate]

i used CosineSimilarity, EuclideanSimilarity, LevenshteinSimilarity and known about how it ...
157 views

### Modify Damerau–Levenshtein distance to allow reversals of longer substrings

Is there a way to modify the Damerau–Levenshtein distance algorithm to allow the transposition of substrings? By this I mean that instead of simply turning "ba" to "ab" you could calculate "worra" to "...
368 views

### Computing the closest match of an automaton and a string

I have a problem where I'm trying to find an efficient algorithm for approximate string matching for an input to the closest string match from an automaton (the input is assumed to be not accepting ...
2k views

### A reference for pseudocode for Monge-Elkan algorithm?

Does anyone have a good reference to pseudocode for Monge-Elkan string comparison algorithm? I have access to the two original papers, but they do not show the pseudocode of the actual algorithm. ...
4k views

### Edit distance (Levenshtein-Distance) algorithm explanation

I want to calculate the edit distance (aka Levenshtein-Distance) between two words: «solo» and «oslo». According to this site we'll get the result matrix: What I don't understand is: In case of ...
396 views

### Complexity of edit distance with block operations

Consider the following problem. I have a pattern $P$ of length $100$ and a text $T$ of length $n$. I want to find the minimum number of operations to transform $P$ into $T$. The operations are: ...
1k 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 ...
943 views

### Is there a basic proof that there exists some edit distance between two strings?

Title says it all pretty much. I do realize that often edit distance is defined as the minimum number of operations needed to transform one string to another, but I want something to point to that's ...
933 views

### Compute minimum hamming distance of a code

How do you find the minimum hamming distance of a code? A naive way is computing the distance of each pair of codewords in our code. It becomes hard when the code is sufficiently large. Is there a ...
2k views

### Find similar vector by Locality Sensitive Hashing

I have many vectors in my database. They are in high dimensions such as: $v_1$ : $\langle 23, 23, 1, 33, 103, 219, \dots \rangle$ $v_2$ : $\langle 92, 83, 1, 33, 239, 192, \dots \rangle$ ... I will ...
374 views

### Semi-local Levenshtein distance

If you have a long string of length $n$ and a shorter string of length $m$, what is a suitable recurrence to let you compute all $n-m+1$ Levevenshtein distances between the shorter string and all ...
75 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 ...
560 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 ...
2k views

### Levenstein distance and dynamic time warp

I am not sure how to draw parallel between the Wagner–Fischer algorithm and dtw algo. In both case we want to find the distance of each index combination (i,j). In Wagner–Fischer, we initiate the ...
2k 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 ...
4k 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 ...
713 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: ...
4k 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 ...
222 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" ...
535 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 ...
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$ ...