Algoritme om foute invoer te detecteren en verbeteren

[palloquin]

Ik ben op zoek naar een (simpele) manier om fouten te detecteren in een nummer reeks.

(klanten krijgen een nummer via een website, moeten dat nummer als referentie gebruiken, en maken daarbij geheid een keer een fout).

Het decteren van de fout is niet zo moeilijk. Ik kan b.v. door middel van een modulus 11 algoritme een controle getal toevoegen aan het einde van van het nummer. (bankrekeningnummer hebben dit).

Maar, mod11 verteld mij alleen DAT er een fout is gemaakt. Niet waar die fout zit. Dus eigenlijk zoek ik een algoritme dat een nummerike string op zo'n manier van een controle voorziet dat als er een schrijf / typ fout wordt gemaakt dat ik 1) kan detecteren dat het nummer niet klopt en 2) een zinnige gok kan doen naar wat het juiste nummer had moeten zijn.

Om het leuk te maken: het liefst moet de klant die dit nummer moet invoeren er niet teveel last van ondervinden...

[NMe]

Als een klant een fout nummer invult, dan moet je helemaal geen algoritme willen dat voor je gaat raden. Want meer dan raden zul je niet kunnen doen. Stel, ik ben een pestkop en geef je een random getal door. Vervolgens gaat jouw algoritme zoeken naar een getal dat daarop lijkt, en ineens ben ik als scammer gekoppeld aan het account van een ander. Lijkt me verre van wenselijk.

Als er een fout gemaakt wordt kun je veel beter contact opnemen met degene die verantwoordelijk is voor het invoeren van dat getal en even navragen. Dat scheelt je een hoop ellende.

Overigens is dit geen programmeer- maar een ontwerpkwestie en daarmee hoort je topic in Software Engineering & Architecture. Zie ook Waar hoort mijn topic?

PRG>>SEA

[ Voor 12% gewijzigd door NMe op 02-09-2006 14:32 ]

[palloquin]

Mijn excuses voor de foute plek

Ik snap dat raden niet zeer wenselijk is, maar het gaat hier om een betalingsreferentie. Stel (en dit gebeurt) dat mensen een keer een fout referentie nummer opgeven bij hun betaling. Dan wil ik kunnen zoeken naar welke betaling bedoeld kan zijn. als ik met enig zekerheid een bepaalde order kan vinden waarvan het nummer overeen komt met het gecorigeerde nummer, en het bedrag ook klopt... Dan ben ik al best blij...

Ik ben nu aan het spelen met een dubbel mod 11... ik post straks nog wel de resultaten...

[NMe]

In principe zou je een Levenshtein afstand kunnen berekenen tussen de ingevoerde waarde en de waarden in je database. Hoe performant dat is durf ik niet te zeggen, maar ik denk niet dat het echt snel gaat werken.

[Rukapul]

Hier moet je niet zelf mee gaan knoeien, maar gewoon zoeken naar een fout corrigerende code (error correcting codes) Coding theory doe je niet zomaar even Overigens zullen de technieken in de aangehaalde Wikipedia pagina zich vooral richten op bit errors. Geen idee of er ook mechanismen zijn die rekening houden met typische menselijke fouten (zoals het omdraaien van 2 getallen, weglaten of invoegen van een getal, of er een fout in typen).

[ Voor 54% gewijzigd door Rukapul op 02-09-2006 15:55 ]

[palloquin]

Hmm... Rukapul zegt hier iets heel verstandigs... ik ging uit van een enkele fout (1 cijfer klopt niet) dat is dan nog wel te verbeteren. Maar mensen zullen idd snel geneigd zijn om b.v. 2 cijfers om te draaien.. en dat maakt mijn gepruts onbruikbaar...

Ik ga kijken op wiki, maar dat ging idd allemaal over bit errors... maar je kan natuurlijk converteren..

[BestTested!]

-NMe- schreef op zaterdag 02 september 2006 @ 15:41:
... Levenshtein afstand...

Rukapul schreef op zaterdag 02 september 2006 @ 15:51:
...fout corrigerende code (error correcting codes) ....

Of je gebruikt ze beide . Je voert eerst een "error correcting code"-algoritme uit. Iets in de vorm van Hamming of Reed Solomon (wel eerst je decimale getal omzetten naar binair). Vind je dan nog geen exacte match (er zijn meer fouten gemaakt dan op te lossen), dan kan je Levenshtein gebruiken om te kijken wat het dichste in de buurt zit.

[Verwijderd]

Ik snap niet waarom er hier over ECC's gepraat wordt, aangezien deze mijns inziens niet van toepassing hoeven te zijn. We hebben immers te maken met een foute invoer. ECC's kan je gebruiken in het geval:
[code]
Verzender van correcte invoer + pariteitsbits/correctiebits/whatever ---- beetje verrotte datalijn --- ontvanger, die de met behulp van de correctiebits weer kan maken
[/code]
Hier hebben we het geval
[code]
Foute invoer --- rechtstreeks naar het systeem
[/code]
Tuurlijk is het mogelijk aan je foute invoer correctiebits toe te voegen, maar daar heb je simpelweg niets aan. Dit zou alleen werken als je de gebruiker van het systeem een goede invoer in laat voeren, op basis hiervan een stel correctiebits berekenen en een willekeurig foute invoer inclusief deze correctiebits aan het systeem voeren. Dan valt er wat te fixen.

In het geval dat je een foute invoer hebt zonder correctie (wat bij dit systeem niet anders kan) zal je moeten kijken, zoals gezegd is naar de afstand tussen de invoer en de mogelijkheden in je database. Een juiste keuze maken op basis van de afstand is verder een koud kunstje lijkt me. Het zou in ieder geval zonde van je tijd zijn je te verdiepen in ECC's aangezien ze niet van toepassing zijn.

Hmm, beter lezen. Aan een nummer wat je zelf aan de klant geeft, kan je natuurlijk prima een flinke lading correctiebits toevoegen. Dan lijkt me inderdaad Hamming of een andere variant dik in orde. Hou er rekening mee dat decimale fouten, bitwise flink kunnen verschillen (15 en 51, 001111 en 110011) waarbij je dus zal moeten kiezen voor véél correctiebits. De kortste klap zal zijn om je klanten een stukje verantwoordelijkheid te geven en ze simpelweg het juiste nummer in te laten voeren. Zonder correctiebits krijg je kleinere ID-nummers en met nummers met minder cijfers worden minder fouten gemaakt. Als je dit nog wat verder doortrekt zou je dus een systeem ontwerpen dat de oplossing bied voor zijn eigen mankement.

[ Voor 22% gewijzigd door Verwijderd op 03-09-2006 12:17 ]

[Verwijderd]

vraag me echt af of dit kan werken,
de gebruiker kan net zo goed de correctiecode fout invoeren?
Of wil je ook een correctiecode op de correctiecode meegeven? en daar weer een correctiecode op?

Je invoercode wordt alleen maar langer wat de kans op fouten weer vergroot.

[ Voor 16% gewijzigd door Verwijderd op 03-09-2006 12:27 ]

[RobIII]

Verwijderd schreef op zondag 03 september 2006 @ 12:24:
vraag me echt af of dit kan werken,
de gebruiker kan net zo goed de correctiecode fout invoeren?
Of wil je ook een correctiecode op de correctiecode meegeven? en daar weer een correctiecode op?

Je invoercode wordt alleen maar langer wat de kans op fouten weer vergroot.

De kans dat een verkeerd ingevoerde correctiecode (of zelfs maar 1 correctie digit achteraan de bestaande code bijv.) matched met de (al dan niet correcte) code is doorgaans dusdanig klein dat je met redelijke zekerheid kunt zeggen dat 1 van de 2 niet goed is.
Een correctie op een correctie maakt dat echt niet beter en is klinkklare onzin.

Voorbeeld: Als ik afspreek dat de "foo-code" altijd deelbaar moet zijn door 7 en mijn code is:

5973562

dan dien ik een laatste "check"-digit toe te voegen (soort parity) om dit getal ( 5 + 9 + 7 + 3 + 5 + 6 + 2 = 37) deelbaar door 7 te maken. De uiteindelijke code wordt dan:

59735625

Nu is het geheel deelbaar door 7 (37 + 5 = 42). De De kans is (relatief) klein dat bij een foute invoer deze "check" toch passed. Dit geldt overigens niet zo zeer voor verwisselde tekens (immers 26537955 klopt ook). Daarvoor is een Levenshtein wel aan te raden.
Overigens is dit maar een voorbeeld. Zo kun je ook de "elfproef" en vele andere error-correcting codes gebruiken. De truuk is natuurlijk om de overhead minimaal te houden (in bovenstaand voorbeeld wordt er maar 1 digit toegevoegd, en dit zou ook werken op een vele malen langere code (met een grotere kans op fouten weliswaar)). Er zijn natuurlijk ook algoritmes te bedenken die (bijv.) voor iedere 4 digits een extra digit toevoegen. De kans op fouten is dan constant(er) maar de overhead wordt ook meer.

Mijn tip: Doe een controle, en wijs de gebruiker er op dat de code niet klopt. Ga er niet naar "raden" wat er niet klopt, dat schept alleen verwarring. Je hebt er veel meer aan om de gebruiker er duidelijk op te wijzen dat er een fout in de code zit met een vriendelijke en uitgebreide help-tekst dan dat je gaat zitten gokken en de gebruiker er dan opeens helemaal geen snars meer van snapt. Als je de gebruiker wijst op z'n fouten zal hij de volgende keer trouwens ook beter opletten, zeker als je 'm wijst op het belang van het invoeren van correcte codes (omdat bijv. anders zijn jackpot naar iemand anders gaat )

[ Voor 56% gewijzigd door RobIII op 03-09-2006 14:12 ]

[Rukapul]

Ik ben 't met RobIII eens dat detectie voldoende is en waarschijnlijk het beste in bestaande bedrijfsprocessen past.

Mocht je toch per se een error correcting code willen toepassen dan kun je op google nog eens zoeken naar decimal error correcting code. Some error correcting codes for certain transposition and transcription errors in decimal integers lijkt precies over dit onderwerp te gaan. (Paper is vast verkrijgbaar via een universiteitsaccount.) De crux is dat de mens nu je 'kanaal' is en dat je error correcting code bij voorkeur geoptimaliseerd wordt voor menselijke fouten

[ Voor 4% gewijzigd door Rukapul op 03-09-2006 14:47 ]

[Verwijderd]

RobIII schreef op zondag 03 september 2006 @ 13:59:
[...]

De kans dat een verkeerd ingevoerde correctiecode (of zelfs maar 1 correctie digit achteraan de bestaande code bijv.) matched met de (al dan niet correcte) code is doorgaans dusdanig klein dat je met redelijke zekerheid kunt zeggen dat 1 van de 2 niet goed is.
Een correctie op een correctie maakt dat echt niet beter en is klinkklare onzin.

was ook sarcastisch bedoeld , TS wil niet foutdetectie maar foutcorrectie, ik denk dat dat onhaalbaar is als je 100% betrouwbaarheid wilt hebben met user invoer.

[MSalters]

100% betrouwbaarheid bestaat simpelweg niet met user invoer, dus elk business proces wat daarop vertrouwt is al defect voordat je ECC introduceert.

[HunterPro]

ik denk dat de TS niet zozeer een klant-op-de-vinger-tik-app wil, maar zodra een klant een betaling heeft gedaan met een verkeerd betalingskenmerk, dat de applicatie voor de ontvangende kant toch nog de administratie rond kan krijgen (en dus 'orphaned' betalingen aan de juiste orders kan knopen). Aan die kant van de orderprocessing is fout'correctie' best mogelijk en toepasbaar.

Klanten maken fouten bij de invoer in hun bankapp/acceptgiro, dus aan de invoerkant kún je dus ook geen op-vinger-tik-acties uithalen. Je moet het aan de processingkant aan elkaar zien te knopen. SAP heeft daar trouwens modules voor die dat errug goed kunnen, en je raadt het goed: die kosten ook een hele boel geld.

Dat zou ik overigens niet op numberguessing doen, maar op verzendend rekeningnummer, naam en bedrag. Maar dat ben ik

[ Voor 32% gewijzigd door HunterPro op 03-09-2006 22:44 ]

[Voutloos]

MSalters schreef op zondag 03 september 2006 @ 22:33:
100% betrouwbaarheid bestaat simpelweg niet met user invoer, dus elk business proces wat daarop vertrouwt is al defect voordat je ECC introduceert.

100% betrouwbaarheid niet, maar fouten corrigerende code werken dan ook doorgaans met 'Maximum likelihood decoding'. En om te zorgen dat er bij een ontvangen woord maar 1 woord is dat het meest waarschijnlijk is, wordt er slimme minimum afstand tussen de mogelijke woorden gebruikt. Maar goed, er zijn al een aantal naampjes genoemd, en 'maximum likelihood decoding' is ook weer een leuke term vor google speur werk.

Overigens wel met je eens dat voor user input alleen foutdetectie handiger is.

[joepP]

palloquin schreef op zaterdag 02 september 2006 @ 16:29:
Hmm... Rukapul zegt hier iets heel verstandigs... ik ging uit van een enkele fout (1 cijfer klopt niet) dat is dan nog wel te verbeteren. Maar mensen zullen idd snel geneigd zijn om b.v. 2 cijfers om te draaien.. en dat maakt mijn gepruts onbruikbaar...

Ik ga kijken op wiki, maar dat ging idd allemaal over bit errors... maar je kan natuurlijk converteren..

Je moet voor elke foute invoer alle openstaande betalingen uit de database ophalen, en de afstand tot die nummers berekenen. Afstand wordt meestal gedefinieerd als het aantal aanpassingen (delete, insert, swap character) om de ene string in de ander te veranderen. Het berekenen hiervan is triviaal en zeer snel voor korte strings. Zolang er niet teveel (zeg: 10.000) openstaande betalingen zijn is dit geen enkel probleem. Zoals al eerder genoemd moet je even zoeken op Levenshtein distance, daar moet genoeg voorbeeldcode van te vinden zijn.