Vi ger nära-täta gränser för att uppskatta redigeringsavståndet mellan två icke-repetitiva strängar (Ulam avstånd) med konstant approximation, i sub-linjär tid. För två strängar av längd d och på redigera avstånd R, vår algoritm körs i tid Õ (d/R + ε d) och utgångar en konstant approximation till R. Vi visar också en matchande lägre bundna (upp till logaritmiska termer). Både övre och nedre gränser är förbättringar jämfört med tidigare resultat från [Andoni-IndykKrauthgamer, SODA'09] respektive [Batu-Ergun-KilianMagen-Raskhodnikova-Rubinfeld-Sami, STOC'03]. Redigeringsavståndet (även kallat Levenshtein-avstånd) mellan två strängar A och B, betecknat ed(A, B), är det minsta antalet teckeninsättningar, raderingar och substitutioner som behövs för att omvandla den ena strängen till den andra. Detta avstånd är av avgörande betydelse inom flera områden såsom beräkningsbiologi och textbehandling, och följaktligen studerades datorproblem med redigeringsavståndet ganska ingående. Ulam metrisk är en specialisering av redigeringsavstånd till icke-repetitiva strängar, där en sträng är icke-repetitiv om varje symbol visas som mest en gång i den. Det finns flera motiv för att studera denna variant. Ur ett praktiskt perspektiv förekommer strängar med begränsade eller inga upprepningar i flera viktiga sammanhang, såsom rangordning av objekt såsom webbsidor (se t.ex. [AJKS02] och [Mar95]). Ur teoretisk synvinkel presenterar Ulam metrisk en konkret vägpunkt mot det svårfångade målet att utforma algoritmer för redigeringsavstånd över allmänna (eller till och med binära) strängar. Det finns två skäl till detta. För det första verkar Ulam metrisk behålla en av de viktigaste svårigheterna med redigeringsavståndet på allmänna strängar, nämligen förekomsten av "missmatchningar" mellan
Nyligen upptäcktes en sublinjär tidsalgoritm för approximering av Ulam-avståndet mellan två permutationer REF.
Near-optimal sublinear time algorithms for Ulam distance
{'venue': "SODA '10", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}