Med tanke på ett sammanhang fritt språk G över alfabetet och en sträng s  en *, språkredigering avstånd problem söker det minsta antalet redigeringar (insättningar, raderingar och substitutioner) som krävs för att konvertera s till en giltig medlem av språket L(G). Den välkända dynamiska programmeringsalgoritmen löser detta problem i O(n 3 ) tid (ignorerar grammatikstorlek) där n är stränglängden [Aho, Peterson 1972, Myers 1985. Trots dess många program, till dags dato finns det ingen algoritm som beräknar den exakta eller ungefärliga språkredigering avståndsproblem i sann subkubisk tid. I den här artikeln ger vi den första algoritmen som beräknar språkredigerar avstånd nästan optimalt. För alla godtyckliga > 0, vår algoritm körs i Õ( n  på poly ( ) ) tid och returnerar en uppskattning inom en multiplikativ approximationsfaktor på (1 + ) med hög sannolikhet, där  och är exponenten för vanlig matris multiplikation av n dimensional kvadratmatriser. Den beräknar också de faktiska redigeringar som krävs. Vi löser vidare det lokala anpassningsproblemet; för alla delsträngar av s, kan vi uppskatta deras språkredigeringsavstånd inom (1 ± ) faktor inÕ( n  på poly( ) ) tid med hög sannolikhet. Därefter utformar vi den allra första subkubiska (Õ(n  ska )) algoritmen som gav en godtycklig stokastisk sammanhangsfri grammatik, och en sträng returnerar en nästan optimal maximal sannolikhet tolkning av den strängen. Stochastic sammanhangsfri grammatik generaliserar betydligt dolda Markov modeller; de ligger på grundval av statistiska naturliga språk bearbetning, och har funnit utbredda tillämpningar inom många andra områden. För att komplettera vårt övre bundna resultat, visar vi att exakt beräkning av maximal sannolikhet tolkning av stokastisk grammatik eller språkredigering avstånd i sann subkubisk tid kommer att innebära en verkligt subkubisk algoritm för alla-par kortaste vägar, en långvarig öppen fråga. Detta kommer att leda till ett genombrott för ett stort antal problem i grafer och matriser på grund av subkubisk likvärdighet. Genom ett känt lägre bundet resultat [Lee 2002], och en ny utveckling [Abboud et al. 2015] även det mycket enklare problemet att tolka en kontextfri grammatik kräver tid. Därför är det osannolikt att någon icke-trivial multiplikativ approximationsalgoritm för något av de två problemen i tid o(n) existerar. Med tanke på en modell för datasemantik och strukturer, är uppskattning av hur väl en datauppsättning passar modellen en kärnfråga i storskalig dataanalys. Formella språk (t.ex. regelbundet språk, sammanhangsfritt språk) ger en generisk teknik för datamodellering. Avvikelsen från en modell mäts med hjälp av de minsta ändringar som krävs i data för att modellen ska passa perfekt. Aho och Peterson studerade denna grundläggande fråga mer än fyrtio år tillbaka för att utforma felkorrigeringstolkar för programmeringsspråk. Med tanke på en sammanhangsfri grammatik (CFG) G över alfabetet och en sträng s  och *, De föreslog språkredigering avstånd problem, som bestämmer det minsta antalet redigeringar (insättningar, raderingar och substitutioner) tillsammans med en redigera skript för att konvertera s till en giltig medlem av L(G). På grund av dess grundläggande natur, språkredigering avstånd problem har funnit många tillämpningar i kompilatoroptimering (terror-korrigering parser [4] Ofta är det naturligt att överväga en probabilistisk generativ modell, och be om den mest sannolika härledning / förklaring av de observerade data enligt modellen. Den stokastiska kontextfria grammatikmodellen (SCFG) är ett exempel på det. Det förknippar en villkorad sannolikhet till varje produktionsregel av en CFG (se definition i avsnitt I-A) som återspeglar sannolikheten för att tillämpa den för att generera medlemmar av språket. SCFGs generaliserar betydligt dolda Markov modeller, och flera stokastiska processer såsom Latent Dirichlet Allocation [20] och Galton-Watson grenningsprocess [28]. De ligger i grunden för statistiska naturliga språk bearbetning, och har funnit utbredda tillämpningar som en rik ram för modellering komplexa fenomen [14], [19], [40], [50]. De mest sannolika
Dessutom visades en (1 + ) - approximation i O(n) tid i REF för alla konstanter > 0.
Language Edit Distance and Maximum Likelihood Parsing of Stochastic Grammars: Faster Algorithms and Connection to Fundamental Graph Problems
{'venue': '2015 IEEE 56th Annual Symposium on Foundations of Computer Science', 'journal': '2015 IEEE 56th Annual Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}