Abstrakt. I många tillämpningar är det nödvändigt att algoritmiskt kvantifiera likheten som visas av två strängar som består av symboler från ett finit alfabet. Ett stort antal liknande åtgärder har föreslagits. Särskilt välkända åtgärder är baserade på redigeringsavstånd och längden på den längsta gemensamma undersekvensen. Vi utvecklar ett begrepp om n-gram likhet och avstånd. Vi visar att redigera avstånd och längden på den längsta gemensamma undersekvensen är specialfall av n-gram avstånd respektive likhet. Vi tillhandahåller formella, rekursiva definitioner av n-gram likhet och avstånd, tillsammans med effektiva algoritmer för att beräkna dem. Vi formulerar en familj av ordlika åtgärder baserade på n-gram, och rapporterar resultaten av experiment som tyder på att de nya åtgärderna överträffar deras Unigram motsvarigheter.
Dessutom generaliserar REF Levenshtein-avståndet med n-grammåttet.
N-gram similarity and distance
{'venue': 'Proc. Twelfth Int’l Conf. on String Processing and Information Retrieval', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}