Denna handledning ger en omfattande översikt över den senaste forskningen om det viktiga problemet med ungefärlig sökning i strängsamlingar. Vi identifierar befintliga index, sökalgoritmer, filtreringsstrategier, teknik för selektivitetsskattning och annat arbete samt kommenterar deras respektive meriter och begränsningar. Textdata är allmänt förekommande. Hanteringen av strängdata i databaser och informationssystem har blivit särskilt viktig på senare tid. Denna handledning fokuserar på följande problem: Med tanke på en samling strängar, identifiera effektivt de som liknar en given frågesträng. En sådan fråga kallas en "ungefärlig strängsökning". Detta problem är av stort intresse för en mängd olika tillämpningar, vilket illustreras av följande exempel. Datarening: Information från flera datakällor har ofta många inkonsekvenser. Till exempel kan samma verkliga enhet representeras i något olika format, såsom "PO Box 23, Main St." och "P.O. Fält 23, Main St". Fel kan också införas på grund av oegentligheter i datainsamlingsprocessen, från mänskliga misstag och många andra orsaker. Av dessa skäl är ett av huvudmålen med datarengöring att hitta liknande enheter i en samling, eller alla liknande par av enheter i ett antal samlingar. Fråga Avkoppling: Ofta nog, användare kan posera SQL frågor till en DBMS som innehåller val predikat som inte matchar alla relevanta data i databasen exakt. Orsakerna är möjliga fel i frågan, inkonsekvenser i uppgifterna, begränsad kunskap om uppgifterna, med mera. Genom att stödja frågeavslappning kan DBMS returnera data av potentiellt intresse till användaren, baserat på frågepredikat likhet (t.ex., returnera "Steven Spielberg" som svar på frågan "Steve Spielberg"). Spell Checking: Med tanke på ett inmatningsdokument, hittar en stavningskontroll potentiella kandidater för ett möjligen feltypat ord genom tillstånd att kopiera hela eller delar av detta material beviljas, förutsatt att kopiorna inte görs eller distribueras för direkt kommersiell fördel, VLDB copyright meddelande och titeln på publikationen och dess datum visas, och meddelande ges om att kopiering är med tillstånd av Very Large Data Base Endowment. För att kopiera på annat sätt, eller för att återpublicera, för att posta på servrar eller för att omfördela till listor, krävs en avgift och/eller ett särskilt tillstånd från förlaget, ACM. VLDB '09, augusti 24-28, 2009, Lyon, Frankrike Copyright 2009 VLDB Endowment, ACM 000-0-0000-00-0/00/00. utför en ungefärlig strängsökning i sitt lexikon. Interactive Search: Ett mycket nytt viktigt program är att ge svar på frågeresultat i realtid, eftersom användare skriver sin fråga (t.ex. en Google-sökruta med en dropdown förslag meny som uppdaterar som användare typ). Sådana interaktiva sökrutor är allmänt förekommande och har visat sig vara mycket viktiga i praktiken, eftersom de begränsar antalet fel som görs av användarna och även minskar antalet omformuleringar av frågor som lämnas in för att hitta den som ger tillfredsställande resultat. Nackdelen med nästan alla befintliga, interaktiva tekniker är att de stöder endast prefix eller substring matcher, utan hänsyn till suddig, ungefärlig sökning; om användare gör ett stavfel, de presenteras med en tom förslagsruta. En anledning är att interaktiv approximativ strängsökning har väckt lite uppmärksamhet och inte är ett trivialt problem att lösa, med tanke på den dyra karaktären av strängliknande funktioner och rankning tekniker. Dessa applikationer kräver ungefärliga-sträng-sök algoritmer med en hög realtid prestanda. Till exempel, överväga en stavningskontroll såsom de som används av Gmail, Hotmail, eller Yahoo! Mail, som måste åberopas många gånger per sekund, för att stödja miljontals samtidiga användare som använder dessa tjänster. Varje begäran om stavningskontroll måste behandlas så snabbt som möjligt. Det är tydligt att högre dataflöde gör det möjligt för servern att betjäna ett mycket större antal användare sömlöst. Ett annat exempel är en företagssökning på en lokal sökmotor (t.ex., YellowPages, Yahoo! Lokala, och Superpages). Det är mycket ofta så att användare felstava företagsnamn (t.ex. "Wall-mart" i stället för "Wal-mart"), och därmed ungefärlig strängsökning i samband med lokal sökning är viktigt. Utföra ungefärlig strängsökning effektivt över de mycket stora strängsamlingar som finns i dessa program är grundläggande för att kunna upprätthålla tusentals användarförfrågningar per sekund. Ett nära relaterat problem är selektivitetsberäkning för ungefärliga string-matchning frågor. Det är av stort intresse att kunna effektivt och korrekt utvärdera selektiviteten i urvalsfrågor i syfte att optimera sökningen (för att utforma effektiva frågeutförandeplaner). Tydligt, selektiviteten av ungefärlig strängmatchning frågor beror i hög grad på den likhet funktion som används. Därför har en mängd olika selektivitetsskattningsalgoritmer redan föreslagits i litteraturen, för olika likhetsfunktioner och baserade på ett varierat antal tekniker (t.ex. histogram, provtagning och klusterbildning).
Ungefärlig strängsökning har studerats ingående i litteraturen (se en utmärkt handledning REF och referenser i den).
Efficient Approximate Search on String Collections
{'venue': 'PVLDB', 'journal': 'PVLDB', 'mag_field_of_study': ['Computer Science']}