Does anyone know of a way to implement an SQL “similar” function?
What I’m looking for is an improvement on the LIKE function. For
example, a statement such as
SELECT * FROM my_dbase WHERE name LIKE '%Smith%"
would return those records containing “Smith”, “Smith & Son”, “Smithson”, etc,
but not “Smyth”. I’d like a statement such as
SELECT * FROM my_dbase WHERE name SIMILAR TO '%Smith%"
such that “Smyth” would also be returned.
Of course, it would be necessary to define “similar”, perhaps with
something like
SELECT * FROM my_dbase WHERE name 50% SIMILAR TO '%Smith%"
Does anyone have any suggestions as to how this could be implemented?
A brute force method with letter-by-letter comparisons seems the
obvious way but this would probably be too slow for databases with
many thousands of records.
for the record… Soundex is crude, and not too accurate… is reduces any word to a letter and 3 numbers… for example my name if I remember boils down to S450 … as to thousands of words that sound nothing like S
Don’t waste your time on Soundex… trust me, the results are totally inaccurate, and you will just be wasting your time… the Soundex Algorithm is super simplistic…
not what I am saying at all… what I am saying is don’t waste your time with Soundex…
I know exactly how it works, and what its pitfalls are. The Levenshtein_distance is way more accurate (and more complex), but even it is not “perfect”…
Likes will only find things that have a similar pattern to the characters, but has nothing to do with what it sounds like…
This works if you can predict all the possible things you want to see as similar, e.g. “y” = “i”, and “ou” = “uo” = “oo”, and so on.
In this case, you can create a new table or add a column to your existing table, in which you put the simplified names, by taking each original name and replace all the possible similarities with one common replacement, i.e. replace any “y” with “i”, and any “uo” and “ou” with “oo”. Then write those simplified names into the new column. Now, when you want to search, you’d simplify your search string with the same replacement function, and then search the new column using the LIKE “%searchstring%” pattern.
This method would be fairly fast, i.e. as fast as your current LIKE … method.
b)
Even faster would be to use Sqlite’s FTS (google it) on this simplified column. That way, using the FTS search, you can, by looking for “Smith”, find “Smithson” and “Smith & sons”, but not “Nosmith” (that’s becausr its lookup goes by word’s beginnings, but is very very fast).
Use an extension to compare the strings
You could also dynamically add a comparison function to the sqlite library. I’ve documented this here: http://blog.tempel.org/2015/09/xojosqliteextensions.html (look for custom function). This is much harder to do, though, and you’ll still have to code the method that will decide what’s similar. Here, the Levenshtein Distance function would perhaps make sense to be used.
That all assumes similar spelling and has nothing to do with “sound”
“PHISH” and “FISH” sound the same… but most algoritms won’t say so, and LIKES and SOUNDEX will both fail (unless you do *ISH)
@Dave S Did you refer to my post above yours? Because my proposed first method would also replace “ph” with “f”, making this a “sound” algorithm Of course, as I wrote, this only works if you can predict all those similarities so that you can hard-code them into the replacement function. Maybe the web has some tables for that, making this easier to build a list of them?
It’s important to know whether you are searching for a single word, or trying to find similarity between samples of multi word text. Depending on this, the viable solutions are significantly different.
There are variants of Soundex, such as Metaphone that are significant improvements. However these are really only suitable for matching of single words, not multi word text samples. However, they are very fast in database applications. Soundex/Metaphone can be calculated once, at the time that the data is entered into the database, and used as an index field. Then, for a search, the Soundex/Metaphone value is calculated only on the search text and then used to find the index value.
Levenshtein Distance is suitable for matching multi word text, but it’s expensive because it has to be calculated for every combination of search text and database text, so you can’t pre-index the database fields with a Levenshtein Distance value without knowing the search text in advance. And, of course, it would be different for every different search text. So, it ends up being a record by record calculation.
[quote=402070:@Dave S]That all assumes similar spelling and has nothing to do with “sound”
“PHISH” and “FISH” sound the same… but most algoritms won’t say so, and LIKES and SOUNDEX will both fail (unless you do *ISH)[/quote]
My name never shows up properly in a Soundex search.
I remember adding a few tweaks before applying standard Soundex to cover a few anomalies like that:
Starts with KN, replace with N (not many silent 'K’s in the middle of words)
Starts with PH, replace with F (PH in the middle becomes 1, ‘bfpv’, so Stephen and Steven match)
Starts with PS , replace with S
EAUX anywhere, replace with a vowel (O)
This was 1988, pre Metaphone, but worked for our data.
Hmm, Metaphone doesn’t account for ‘EAUX’
Of course, as I wrote, this only works if you can predict all those similarities so that you can hard-code them into the replacement function. Maybe the web has some tables for that, making this easier to build a list of them?