|
in reply to Finding Nearly Identical Sets
A few questions:
- You already have the set of known 9-digits numbers to compare against?
If so, how are they currently stored?
If not, will you just take the numbers from the first batch as 'good'?
Or are you hoping to cross-check the first batch against the second and detect errors that might be in the first set?
If you have a known good set, then it is simply a case of checking if the number found already exists in that known set, and that can be done very quickly using a 106MB bitstring.
- You already have a method of finding & extracting the number from the message; even if it is 8 or 10 digits.
Ie. Its location is fixed, or clearly prefixed, or it will be the only large (say more than 7-digits) number in the message.
What I'm getting at here is the insertions or deletions are easily detected, because the numbers are the wrong length. That only really leaves transpositions to detect?
With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
In the absence of evidence, opinion is indistinguishable from prejudice.
|
Re^2: Finding Nearly Identical Sets
by Limbic~Region (Chancellor) on Sep 28, 2016 at 17:33 UTC
|
BrowserUk,
I am going to answer some of your questions out of order (easiest to answer to hardest).
You already have a method of finding & extracting the number from the message; even if it is 8 or 10 digits.
Correct
What I'm getting at here is the insertions or deletions are easily detected, because the numbers are the wrong length. That only really leaves transpositions to detect?
Incorrect. While it is trivial to determine that a mistake has been made, it isn't necessarily trivial to determine what the mistake was (which set the number should have been).
You already have the set of known 9-digits numbers to compare against?
No. Think of it this way. The set represents what should be a unique identifier for the message sender. The first time I receive a message with a valid set (meets my aforementioned criterion) that doesn't appear to be similar to any other previously seen set - I will use that set to identify that sender. Not because it is correct but because it was first. A subsequent message from that sender may be objectively correct but for my purposes I don't know - I only know that it is nearly identical to what I have already seen.
If so, how are they currently stored?
I'm still figuring that out but because there will be parallel processing going on, I am assuming it will be in a database and finding good candidates will need to be 1 or more index based queries.
Hopefully I have answered all of your questions satisfactorily enough to advance the problem but my cold medicine is really doing a number on my cognitive abilities.
| [reply] |
|
|
a valid set
When you say "set", you're referring to one group of nine, single digits? (I'm wondering why "set" rather than just 'number'?)
With nine digits, 1 .. 9, there are 888,888,888 possibilities; how many of those do you expect to be "receiving"?
Over what time period? Do you reset at any point?
With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
In the absence of evidence, opinion is indistinguishable from prejudice.
| [reply] |
|
|
BrowserUk,
I was trying to reduce the problem down to only the parts that matter. Through out the message, there are 10 markers - I am extracting and only interested in 9 of them. It is weird and highly domain specific (which I can't discuss).
This "set" of numbers for a given message is valid over a few days (let's say 10 days tops). The reset happens when the sender's right to send expires and they are removed so it is possible for the same numbers to be re-used at some point in the future but they would be considered "new" then. At any one time, I think I would have around 500K of the nearly 900 million possible.
| [reply] |
|
|
Re^2: Finding Nearly Identical Sets
by Limbic~Region (Chancellor) on Sep 28, 2016 at 18:36 UTC
|
BrowserUk,
If it helps, you don't have to think of them as sets but as strings or numbers (driver's license, passport, employee ID, etc.) with the understanding that they are expected to not contain zero anywhere and should be a length of 9.
For instance, let's say the program has '198472385'
- Is it less than 8 characters long? If yes, abort
- Is it more than 10 characters long? If yes, abort
- Has this "thing" already been seen? If yes, we are done
- Has a variation of this thing been seen (same digits but in a different order)? If yes, we are done
- Are there any other "things" nearly identical to this one regardless of the order of the digits (can I transform this "thing" into a previously seen "thing" with exactly one operation (insert, delete, transform))? If yes, which ones?
Items 1 - 4 are obviously trivial. I don't even need to be perfect with number 5 though that would make me happy. I am trying to find a way to quickly/cheaply find candidates to number 5.
One way to do it would be just to have a bunch of indices. For instance, for "a single digit has been transformed".
- When storing - sort the set
- For each of the 9 possible positions that could be changed in the future, assume each one was in fact changed and remove that character and concatenate the remaining 8 characters into an index/hash
- When checking candidates, duplicate the process above checking all 9 indices for an exact match
The above scenario would work perfectly for transforms but requires you to maintain 9 different indices and the searches are ugly.
| [reply] |
|
|
