I need to compare strings to decide whether they represent the same thing. This relates to case titles entered by humans where abbreviations and other small details may differ. For example, consider the following two titles:
std::string first = "Henry C. Harper v. The Law Offices of Huey & Luey, LLP";
As opposed to:
std::string second = "Harper v. The Law Offices of Huey & Luey, LLP";
A human can quickly gauge that these are most likely one and the same. The current approach I have taken is to normalize the strings by lowercasing all letters and removing all punctuation and spaces giving:
std::string firstNormalized = "henrycharpervthelawofficesofhueylueyllp";
And:
std::string secondNormalized = "harpervthelawofficesofhueylueyllp";
Comparing in this case, one is a sub-sequence of the other, but you can imagine other more complex variations where that does not necessarily occur, yet they have significant sub-sequences in common. There could also be occasional human entry errors such as transposed letters and spelling errors.
Perhaps some kind of character diff program could help? I've seen good line diff programs for comparing differences in code to be checked in, is there something like that on a character basis, maybe in boost? If you could count the number of consecutive characters in common and take the ratio to the characters unshared, perhaps that would be a good heuristic?
In the end, I need a Boolean decision as to whether to consider them the same or not. It doesn't have to be perfect, but it should ideally rarely be wrong.
What algorithm can I use that will give me some kind of quantification as to how similar the two strings are to each other which I can then convert into a yes/no answer by way of some heuristic?
Using String. equals() :In Java, string equals() method compares the two given strings based on the data/content of the string. If all the contents of both the strings are same then it returns true.
There are three ways to compare String in Java: By Using equals() Method. By Using == Operator. By compareTo() Method.
Similarity algorithms compute the similarity of pairs of nodes based on their neighborhoods or their properties. Several similarity metrics can be used to compute a similarity score.
What you're looking for are called String Metric algorithms. There a significant number of them, many with similar characteristics. Among the more popular:
Have a look at these as well as others on the wiki page on the topic.
Damerau Levenshtein distance is another algorithm for comparing two strings and it is similar to the Levenshtein distance algorithm. The difference between the two is that it can also check transpositions between characters and hence may give a better result for error correction.
For example: The Levenshtein distance between night
and nigth
is 2 but Damerau Levenshtein distance between night
and nigth
will be 1 because it is just a swap of a pair of characters.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With