2
$\begingroup$

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], b = [0, 2, 1, 3, 4], and c = [1, 4, 2, 0, 3]. Is there a function to determine that a is closer to b than c is?

So the function I am looking for I think should be similar to SHA, but without the avalanche effect. The examples I give is using arrays of integers, but obviously this should also work on any arbitrary stream of data.

$\endgroup$
  • $\begingroup$ I don't think a hash function is what you need at all. Do your arrays always have the same entries, but in a different order? It seems that either string similarity or similarity functions on time series would be more helpful, but that depends on what this 'closeness' is. Could you be more specific about what you're going to use this 'closeness' for? $\endgroup$ – Discrete lizard Jan 19 '18 at 8:36
  • $\begingroup$ Well, I have many arrays of integers with arbitrary sizes and elements in them. They are not following any particular pattern or order, and some have duplicate elements. I am trying to find which arrays are "close" to each other so I can group them based on their similarity. In the example above, I would group a and b together, but c would belong to a separate category, unless there are other arrays in the dataset such that the difference between a and c are negligible compared to other arrays. $\endgroup$ – garbagecollector Jan 19 '18 at 8:53
  • $\begingroup$ I have thought of a solution, and that's just by comparing each element, and adding 1 for every element that is not the same. However, I am wondering if there's a more formal algorithm. $\endgroup$ – garbagecollector Jan 19 '18 at 9:18
3
$\begingroup$

There are many measures of similarity between sequences (or arrays or even strings), which one to use depends on the specific goals for the similarity. It may be the case that some trial and error is required to find the 'best' one. Therefore, I'll give a brief overview of some well-known similarity measures:

First, I consider distances most commonly associated with strings:

  • Edit distance: Here, we count minimum the number of 'edit operations' required to transform string $A$ into string $B$. These edit operations are usually inserting, deleting or substituting a single character in your string or array. Usually, the different operations have different costs. The Levenshtein distance is a special case of the edit distance that is commonly used to compare words.

  • Hamming distance: This distance simply counts the number of indices between two sequences that differ, which is the same method you described in your comment. This can at times be a decent metric, but it often doesn't come close to an our intuitive notion of 'similarity'.

There are many more string metrics, but those above are the most commonly known.

Next, you could also consider metrics over time series: here the sequences are interpreted as measurements at increasing time-steps. Usually, we assume there is some distance measure over the individual elements of your sequences, this can be taken as simply $d(x,y) = \begin{cases} 0 & \text{if $x=y$}\\ 1 & \text{if $x\neq y$}\end{cases}$, if you don't have a more reasonable notion of distance between your characters.

  • Dynamic Time Warping (DTW): This distance finds a suitable 'alignment' between the pair of sequence that minimizes the sum of the distances between the alignment. An advantage of this method is that this measure is insensitive to 'time shifts': The sequences $A=\langle 1, 2,3,4,5 \rangle$ and $B=\langle 0 ,1, 2,3,4\rangle$ have maximum Hamming distance, but a low DTW distance, as DTW is allowed to match the element $A[1]$ to $B[2]$, $A[2]$ to $B[3]$ and so on. Computing the DTW between two sequences takes $O(n^2)$ time (if both sequences have length $n$), but there are many faster approximations and heuristic speed-ups.

  • Longest Common Subsequence (LCS): This isn't always used as a similarity measure, but the length of a LCS between two sequences $A$ and $B$ can be seen as inversely proportional to the distance between $A$ and $B$ (i.e. long common subsequences mean high similarity). A disadvantage of this measure is that it often ignores too much of the relevant structure of the sequences, but it sometimes works fine.

Other similarity measures for time series can be found here.

$\endgroup$
  • $\begingroup$ Thank you for the breakdown. Exactly what I am looking for. I guess for starter, I can use my own (Hamming distance), but I can see the ideal solution for my case would be something similar to the LCS. $\endgroup$ – garbagecollector Jan 19 '18 at 11:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.