Levenshteinoutomaat

in Wikipedia, die vrye ensiklopedie
Spring na: navigasie, soek

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).

Verwysings[wysig]