Hash-like algorithm with “weighted” input

Question

The title is not the best but since I have no clue what I'm actually searching I simply used something broad. I'm searching for a an algorithm, a class of algorithms or at least keywords I can use for further research.

Essentially I'm searching for a hash-like function that takes an input and boils it down to a much more compact representation. I want similar inputs to be somewhat near each other and I want certain parts of the input to be weighted higher/lower than other parts. I don't care how the distance is as long as I have a partial ordering so I can group similar entries together.

As an example lets assume I have the Input strings:

A = alittlebeer
B = alittlebear
C = blittlebear

And lets assume that I define my weight so that I weight the first 3 characters much higher than the rest. Then I would expect that $|f(A) - f(B)| << |f(B) - f(C)| < |f(C) - f(A)|$

Answer 1

Usually, k-means clustering is used for grouping words and the technique proposed here: https://stackoverflow.com/questions/13769242/clustering-words-into-groups could be used to calculate distance words.

However, I think a kd-tree may be a more suitable technique to sort the words according to their distances. Here, the maximum character length of A,B or C would be the dimension of the tree. The first character of the string is the first dimension, the second character is the second D... and so on. Search and insert operation would be fast and the first 3 characters will naturally carry more weight than the rest.

Hope this helps.

Answer 2

I believe you may want to have a look at string metrics: http://en.wikipedia.org/wiki/String_metric

These algorithms basically attempt to define a set of similarity metrics. You could order a list of strings by using an anagram model of the string to calculate an ordering metric. The anagram model is your primitive hash, or primary key. Anagrams are overly simplistic, but hopefully you see what I mean.

Levenshtein distance is a very well known similarity algorithm.

Answer 3

This would be a naive suggestion rather than a solution:

1. Consider each string a series of numbers from ASCII mapping. This defines the closeness of letters.

2. Declare a container of input, which is a vector of a max length. Now give a weight vector of the same length.

3. Sort every input based on the given weight vector, then greedily match letters from the starts of the inputs to their ends. The earlier the mismatch occurs, the larger the distance between the inputs is.

4. To quantify the distance, let's say we use this non-interpretable naive formula:

Distance = exp(100 + mismatch-weight) + mismatch-weight * ASCII-difference

This is a greedy approach. I'm ignoring the fact that there may be a large number of mismatch in the strings. Neither is the distance metric meaningful at all.