Most frequent k chars distance: Difference between revisions

The string distance

Method has two steps.

* [[wp:Hash function|Hash]] input strings str1 and str2 separately using MostFreqKHashing and output hstr1 and hstr2 respectively

* Calculate string distance (or string similarity coefficient) of two hash outputs, hstr1 and hstr2 and output an integer value

The first step of algorithm is calculating the hashing based on the most frequent k characters. The hashing algorithm has below steps:

'''string function''' ''MostFreqKHashing'' ('''string''' inputString, '''int''' K)

Similar to the most of [[wp:hashing function|hashing functions]], ''Most Frequent K Hashing'' is also a [[wp:one way function]].

Distance calculation between two strings is based on the hash outputs of two strings.

'''int function''' ''MostFreqKSimilarity'' ('''string''' inputStr1, '''string''' inputStr2)

In some implementations, the distance metric is required instead of similarity coefficient. In order to convert the output of above similarity coefficient to distance metric, the output can be subtracted from any constant value (like the maximum possible output value). For the case, it is also possible to implement a [[wp:wrapper function]] over above two functions.

In order to calculate the distance between two strings, below function can be implemented

'''int function''' MostFreqKSDF ('''string''' inputStr1, '''string''' inputStr2, '''int''' K, '''int''' maxDistance)

Any call to above string distance function will supply two input strings and a maximum distance value. The function will calculate the similarity and subtract that value from the maximum possible distance. It can be considered as a simple [[wp:additive inverse]] of similarity.

Let's consider maximum 2 frequent hashing over two strings ‘research’ and ‘seeking’.

<lang javascript>MostFreqKHashing('research',2) = 'r2e2'</lang>

MostFreqKSDF(str1,str2,2,100) = 83

</pre>

=={{header|C++}}==

It computes the identical value on the identical inputs.

{{reflist}}