Det finns ett brett spektrum av applikationer som kräver att fråga en stor databas av texter för att söka efter liknande strängar eller understrängar. Traditionell ungefärlig delsträngsmatchning kräver att en användare anger en likhetströskel. Utan topk ungefärlig substring matchning, användare måste prova upprepade gånger olika högsta avstånd tröskelvärden när den korrekta tröskeln är okänd i förväg. I vårt papper föreslår vi först effektiva algoritmer för att hitta toppk ungefärliga substring matchar med en given frågesträng i en uppsättning datasträngar. För att minska antalet dyra distansberäkningar använder de föreslagna algoritmerna våra nya filtreringstekniker som drar nytta av q-gram och inverterade q-gramindex som finns tillgängliga. Vi utför omfattande experiment med verkliga datamängder. Våra experimentella resultat bekräftar effektiviteten och skalbarheten hos våra föreslagna algoritmer.
Kim och Al. REF studerade problemet med toppk ungefärlig delsträngsmatchning.
Efficient top-k algorithms for approximate substring matching
{'venue': "SIGMOD '13", 'journal': None, 'mag_field_of_study': ['Computer Science']}