I'm trying to develop a way of taking an entity with a number of properties and searching for similar entities in the database (matching as many of the properties in the correct order as possible). The idea is that it would then return a % of how similar it is.
The order of the properties should also be taken into account, so the properties at the beginning are more important than the ones at the end.
For example:
Item 1 - A, B, C, D, E
Item 2 - A, B, C, D, E
Would be a 100% match
Item 1 - A, B, C, D, E
Item 2 - B, C, A, D, E
This wouldn't be a perfect match as the properties are in a different order
Item 1 - A, B, C, D, E
Item 2 - F, G, H, I, A
Would be a low match as only one property is the same and it is in position 5
This algorithm will run for thousands and thousands of records so it needs to be high performing and efficient. Any thoughts as to how I could do this in PHP/MySQL in a fast and efficient manner?
I was considering levenshtein but as far as I can tell that would also look at the distance between two completely different words in terms of spelling. Doesn't appear to be ideal for this scenario unless I'm just using it in the wrong way..
It might be that it could be done solely in MySQL, perhaps using a full text search or something.
This seems like a nice solution , though not designed for this scenario. Perhaps binary comparison could be used in some way?
Source: Tips4all, CCNA FINAL EXAM
what i'd do is encode the order and property value into a number. numbers have the advantage of fast comparisons.
ReplyDeletethis is a general idea and may still need some work but i hope it would help in some way.
calculate a number (some form of hash) for each property and multiply the number representative of the order of appearance the property for an item.
say item1 has 3 properties A, B and C.
hash(A) = 123, hash(B) = 345, hash(C) = 456
then multiply that by the order of appearance given that we have a know number of properties:
(hash(A) * 1,000,00) + (hash(B) * 1,000) + (hash(C) * 1) = someval
magnitude of the multiplier can be tweaked to reflect your data set. you'll have to identify the hash function. soundex maybe?
the problem is now reduced to a question of uniqueness due to hash collisions but we can be pretty sure about properties that don't match.
also, this would have the advantage of relative ease of checking if a property appears in another item in different order by using the magnitude of the multiplier to extract the hash value from the number generated.
HTH.
edit: example for checking matches
given item1(a b c) and item2(a b c). the computed hash of items would be equal. this is a best case scenario. no further computations are required.
given item1(a b c) and item2(d e a). computed hash of items are not equal. proceed to breaking down property hashes...
say a hash table for properties a = 1, b = 2, c = 3, d = 4, e = 5 with 10^n for multiplier. computed hash for item1 is 123 and item2 is 451, break down the computed hash for each property and compare for all combinations of properties one for each item1 (which becomes item1(1 2 3) ) and item2 (which becomes item2(4 5 1) ). then compute the score.
another way of looking at it would be comparing the properties one by one, except this time, you're playing with numbers instead of the actual string values
You can draw inspiration (or flat out algorithms) from various sequence alignment algorithms like Smith-Waterman. Indeed what you're looking for very much seems to be a description of sequence alignment. I am, however, uncertain if it's even possible to do this as an SQL query.
ReplyDelete