The string similarity metrics mentioned here can all work. However, further normalization of your text in very specific ways can lead to much better results.
TL;DR
From my experience in speech recognition and handwriting recognition, I think your problem will be best solved by using Text Normalization (archived) followed by a Word Error Rate (archived).
A good, quick overview of this process is given at an Amazon AWS Machine Learning Blog post on Evaluating Speech Recognition (archived). A good (somewhat standard) tool for doing both parts of the process (normalization and scoring) is NIST's SCTK. First use rfilter1
for the text normalization, then use sclite
to get the score. Figure out based on the score which strings you consider to match.
Further details
I think that there are three areas of study/application which the problems faced are very similar to your problem. They are: 1) Speech Recognition (archived) (a domain "where abbreviations and other small details may differ"); and in the related solutions of 2) Optical Character Recognition (archived) and 3) Handwriting Recognition (archived) (both domains "where [data is] entered by humans [and] where abbreviations and other small details may differ".).
It's especially useful to look at the scoring of automated or human transcribers/recognizers and at the problem of searching for strings in any such transcription. From my experience in these domains, it seems that the best similarity comparisons come from Levenshtein Distance (archived) using words instead of characters for finding the edit distance; this is called the Word Error Rate. A normalization of text, including case, punctuation, and such things as abbreviations, makes the comparison even better.
A Quick Example
It seems you're using C
or C++
. sclite
and rfilter1
are mostly written in C
. I hope that an example using bash
+sclite
will suffice.
Contents of law.glm
, a VERY minimal GLM
file (GLobal Mapping file, i.e. pairs of search and replace rules)
;;
* name "law.glm"
* desc "Showing extra normalization"
* format = "NIST1" ;; other option is NIST2
* max_nrules = "1000" ;; allocating space (I can update this if necessary)
* copy_no_hit = "T" ;; don't ignore the line if there isn't a match
* case_sensitive = "F"
. => / __ [ ] ;; changes only if there's a space after it
, => / __ [ ]
? => / __ [ ]
! => / __ [ ]
versus => v / [ ] __ [ ] ;; changes only if there's a space before & after
vs => v / [ ] __ [ ]
& => and / [ ] __ [ ]
llp => limited liability partnership / [ ] __ [ ]
llc => limited liability company / [ ] __ [ ]
it's => it is / [ ] __ [ ]
shoppe => shop / [ ] __ [ ]
mister => Mr / [ ] __ [ ]
Now, in bash
.
$ first="Henry C. Harper v. The Law Offices of Huey & Luey, LLP (spk1_1)"
$ second="Harper v. The Law Offices of Huey & Luey, LLP (spk1_1)"
#
# sclite requires actual files.
# It also requires something after the string (an ID, which has been
#+ put in as '(spk1_1)', don't worry about the details.)
#
$ echo "${first}" > first.txt
$ echo "${second}" > second.txt
#
# normalization
$ rfilter1 law.glm < first.txt > first_glm_normalized.txt
$ tr [A-Z] [a-z] < first_glm_normalized.txt > first_normalized.txt
$ rfilter1 law.glm < second.txt > second_glm_normalized.txt
$ tr [A-Z] [a-z] < second_glm_normalized.txt > second_normalized.txt
#
# Run the scorer (similarity finder)
$ sclite -r first_normalized.txt -h second_normalized.txt -i rm -o snt stdout
===============================================================================
SENTENCE LEVEL REPORT FOR THE SYSTEM:
Name: second_normalized.txt
===============================================================================
SPEAKER spk1
id: (spk1_1)
Scores: (#C #S #D #I) 12 0 2 0
REF: HENRY C harper v the law offices of huey and luey limited liability partnership
HYP: ***** * harper v the law offices of huey and luey limited liability partnership
Eval: D D
Correct = 85.7% 12 ( 12)
Substitutions = 0.0% 0 ( 0)
Deletions = 14.3% 2 ( 2)
Insertions = 0.0% 0 ( 0)
Errors = 14.3% 2 ( 2)
Ref. words = 14 ( 14)
Hyp. words = 12 ( 12)
Aligned words = 14 ( 14)
-------------------------------------------------------------------------------
$ # That `-i rm' has to do with that ID we talked about
So, there's a 14.3% Word Error Rate.
Now, let's look at a law case name that shouldn't match.
$ third="Larry Viola versus The Law Office of Mister Scrooge McDuck, Limited Liability Corporation (spk1_1)"
$ echo "${third}" > third.txt
$ rfilter1 law.glm < third.txt > third_glm_normalized.txt
$ tr [A-Z] [a-z] < third_glm_normalized.txt > third_normalized.txt
#
$ sclite -r first_normalized.txt -h third_normalized.txt -i rm -o snt stdout
$ sclite -r first_normalized.txt -h third_normalized.txt -i rm -o snt stdout ===============================================================================
SENTENCE LEVEL REPORT FOR THE SYSTEM:
Name: third_normalized.txt
===============================================================================
SPEAKER spk1
id: (spk1_1)
Scores: (#C #S #D #I) 6 7 1 0
REF: HENRY C HARPER v the law OFFICES of HUEY AND LUEY limited liability PARTNERSHIP
HYP: ***** LARRY VIOLA v the law OFFICE of MR SCROOGE MCDUCK limited liability CORPORATION
Eval: D S S S S S S S
Correct = 42.9% 6 ( 6)
Substitutions = 50.0% 7 ( 7)
Deletions = 7.1% 1 ( 1)
Insertions = 0.0% 0 ( 0)
Errors = 57.1% 8 ( 8)
Ref. words = 14 ( 14)
Hyp. words = 13 ( 13)
Aligned words = 14 ( 14)
-------------------------------------------------------------------------------
$ # This one has a 57.1% Word Error Rate
You'll likely need to run some of your strings through the scoring (comparison) process to come up with a heuristic of where to separate True
from False
.