Levenshteinoutomaat
| Hierdie artikel is 'n weesbladsy. Dit is nie geskakel of in ander bladsye ingesluit nie. Help Wikipedia deur na moontlike teks te soek en 'n skakel hierheen te plaas. |
In rekenaarwetenskap is Levenshteinoutomate 'n familie eindigetoestandoutomata wat die versameling V van alle woorde in 'n formele taal waarvoor die Levenshteinafstand tot 'n arbitrêre woord W nie 'n bepaalde konstante oorskry nie, kan herken. 'n Levenshteinoutomaat vir W kan in lineêre tyd eweredig aan die lengte van W gekonstrueer word, en kan V in baie minder tyd identifiseer as wat nodig sou wees as die Levenshteinafstand na W vir elke woord in die taal bereken sou word ('n probleem met kwadratiese tydkompleksiteit).
Bron wysig
- Klaus U. Schulz, Stoyan Mihov, Fast String Correction with Levenshtein-Automata. International Journal of Document Analysis and Recognition, 5(1):67--85, 2002.
