इनपुट के लिए सबसे समान स्ट्रिंग खोजने का सबसे तेज़ तरीका?

Question

एक क्वेरी स्ट्रिंग को देखते हुए लंबाई लंबाई क्यू, और लंबाई की एम अनुक्रमों की सूची एल वास्तव में एन, क्यू में सबसे कम मिलान स्थिति के साथ एल में स्ट्रिंग को खोजने के लिए सबसे कुशल एल्गोरिदम क्या है? उदाहरण के लिए:

Q = "ABCDEFG"; 
L = ["ABCCEFG", "AAAAAAA", "TTAGGGT", "ZYXWVUT"]; 
answer = L.query(Q); # Returns "ABCCEFG" 
answer2 = L.query("AAAATAA"); #Returns "AAAAAAA". 

स्पष्ट तरीका है एल में प्रत्येक अनुक्रम को स्कैन करना, खोज को ओ (एम * एन) लेना। क्या सबलाइनर समय में ऐसा करने का कोई तरीका है? मुझे कोई परवाह नहीं है कि एल को कुछ डेटा संरचना में व्यवस्थित करने के लिए बड़ी अग्रिम लागत है क्योंकि इसे कई बार पूछताछ की जाएगी। साथ ही, बंधे स्कोर को मनमाने ढंग से संभालना ठीक है।

संपादित करें: स्पष्टीकरण के लिए, मैं हैमिंग दूरी की तलाश में हूं।

Answer 1

मुझे लगता है कि आप Levenshtein edit distance देख रहे हैं।

few questions here on SO about this already हैं, मुझे लगता है कि आप कुछ अच्छे उत्तर पा सकते हैं।

Answer 2

आप प्रत्येक अनुक्रम को एन-आयामी समन्वय के रूप में देख सकते हैं, परिणामस्वरूप स्थान को ब्लॉक में बदल सकते हैं जो जानते हैं कि उनमें कौन से अनुक्रम होते हैं, फिर एक लुकअप पर पहले खोज अनुक्रम के ब्लॉक और सभी संगत ब्लॉक खोजें, फिर आवश्यकतानुसार विस्तार करें । (बेडौल के कई कार्यक्षेत्रों को बनाए रखने शायद खोज ब्लॉकों की वास्तव में बड़े समूहों में हो रही की तुलना में अधिक वांछनीय है।)

Answer 3

best-first search लक्ष्य दृश्यों पर से कुछ किस्म ओ (एम * एन) की तुलना में बेहतर करेंगे। इसका मूल विचार यह है कि आप लक्ष्य अनुक्रमों के पहले चरित्र के साथ अपने उम्मीदवार अनुक्रम में पहले वर्ण की तुलना करेंगे, फिर आपके दूसरे पुनरावृत्ति में केवल अनुक्रमों के साथ अगली-चरित्र तुलना करें, जिनमें कम से कम विसंगतियों की संख्या है, और इसी तरह। आपके पहले उदाहरण में, आप दूसरी बार ABCCEFG और AAAAAAA के विरुद्ध तुलना करना चाहते हैं, ABCCEFG केवल तीसरे और चौथे बार, सभी अनुक्रम पांचवें बार, और इसके बाद केवल ABCCEFG। जब आप अपने उम्मीदवार अनुक्रम के अंत तक पहुंच जाते हैं, तो न्यूनतम मिलान मिलान के साथ लक्ष्य अनुक्रमों का सेट आपका मिलान सेट होता है।

(नोट:।। हर कदम आप कि खोज प्रगतिशील तुलना में से कोई भी वर्ण छोड़ की शाखा के लिए अगले वर्ण के खिलाफ तुलना कर रहे हैं पर)

Answer 4

आप तार के बीच Hamming distance लिए देख रहे हैं (यानी समकक्ष स्थानों पर विभिन्न पात्रों की संख्या)?

या वर्णों के बीच "बीच" दूरी (जैसे अंग्रेजी अक्षरों के ASCII मानों के बीच अंतर) आपके लिए भी महत्वपूर्ण है?

Answer 5

Locality sensitive hashing जो कि इस review article in CACM से समझ में आता है, के रूप में जाना जाता है, के रूप में जाना जाता है। कहा लेख बहुत बालों वाली है और मैंने इसे सब कुछ नहीं पढ़ा। nearest neighbor search भी देखें।

अपनी समस्या से इन संदर्भों को जोड़ने के लिए: वे सभी एक मीट्रिक स्पेस, जैसे एन-आयामी वेक्टर स्पेस में बिंदुओं के एक सेट से निपटते हैं। आपकी समस्या में, n प्रत्येक स्ट्रिंग की लंबाई है, और प्रत्येक समन्वय पर मान वे वर्ण हैं जो स्ट्रिंग में प्रत्येक स्थिति में दिखाई दे सकते हैं।

Answer 6

यदि आगे की लागत कोई फर्क नहीं पड़ता है तो आप हर संभव इनपुट के लिए सबसे अच्छे मैच की गणना कर सकते हैं, और परिणाम को हैश मानचित्र में डाल सकते हैं।

बेशक यह काम नहीं करेगा अगर एन बेहद छोटा नहीं है।

Answer 7

मैं एक सामान्य, सटीक एल्गोरिदम के बारे में नहीं सोच सकता जो ओ (एन * एम) से कम होगा, लेकिन यदि आपके पास पर्याप्त छोटा एम और एन है तो आप एक एल्गोरिदम बना सकते हैं जो (एन + एम) बिट-समांतर संचालन का उपयोग करना।

उदाहरण के लिए, यदि एन और एम दोनों 16 से कम हैं, तो आप 64 बिट इनट्स (16 * लॉग 2 (16) = 64) की एन * एम लुकअप टेबल का उपयोग कर सकते हैं, और सभी कार्यों को एक पास में कर सकते हैं स्ट्रिंग, जहां काउंटर में 4 बिट्स का प्रत्येक समूह स्ट्रिंग मिलान में से एक के लिए 0-15 की गणना करता है। जाहिर है आपको काउंटर स्टोर करने के लिए एम लॉग 2 (एन + 1) बिट्स की आवश्यकता है, इसलिए प्रत्येक चरित्र के लिए कई मानों को अपडेट करने की आवश्यकता हो सकती है, लेकिन अक्सर एक ही पास लुकअप अन्य दृष्टिकोणों की तुलना में तेज़ हो सकता है। तो यह वास्तव में ओ (एन * एम लॉग (एन)) है, केवल निचले स्थिर कारक के साथ - 64 बिट इंट्स का उपयोग करके इसमें एक 1/64 प्रस्तुत होता है, इसलिए लॉग 2 (एन) < 64 यदि बेहतर है तो लॉग होना चाहिए। यदि एम लॉग 2 (एन +1) < 64, यह (एन + एम) संचालन के रूप में काम करता है। लेकिन यह उप-रैखिक की बजाय अभी भी रैखिक है।

#include <stdint.h> 
#include <stdlib.h> 
#include <stdio.h> 
#include <inttypes.h> 

size_t match (const char* string, uint64_t table[][128]) ; 

int main() 
{ 
    const char* data[] = { "ABCCEFG", "AAAAAAA", "TTAGGGT", "ZYXWVUT" }; 
    const size_t N = 7; 
    const size_t M = 4; 

    // prepare a table 
    uint64_t table[7][128] = { 0 }; 

    for (size_t i = 0; i < M; ++i) 
     for (size_t j = 0; j < N; ++j) 
      table[j][ (size_t)data[i][j] ] |= 1 << (i * 4); 

    const char* examples[] = { "ABCDEFG", "AAAATAA", "TTAGQQT", "ZAAGVUT" }; 

    for (size_t i = 0; i < 4; ++i) { 
     const char* q = examples[i]; 
     size_t result = match (q, table); 

     printf("Q(%s) -> %zd %s\n", q, result, data[result]); 
    } 
} 

size_t match (const char* string, uint64_t table[][128]) 
{ 
    uint64_t count = 0; 

    // scan through string once, updating all counters at once 
    for (size_t i = 0; string[i]; ++i) 
     count += table[i][ (size_t) string[i] ]; 

    // find greatest sub-count within count 
    size_t best = 0; 
    size_t best_sub_count = count & 0xf; 

    for (size_t i = 1; i < 4; ++i) { 
     size_t sub_count = (count >>= 4) & 0xf; 

     if (sub_count > best_sub_count) { 
      best_sub_count = sub_count; 
      best = i; 
     } 
    } 

    return best; 
} 

Answer 8

सर्वोत्तम उत्तर एल्गोरिदम का उल्लेख करने वाले को छोड़कर सभी उत्तरों बहुत अधिक हैं। स्थानीय रूप से संवेदनशील हैशिंग मूल रूप से सपने देख रहा है। यह पहली बार है जब मैं स्टैक ओवरफ्लो पर बहुत अधिक जवाब देखता हूं।

सबसे पहले, यह एक कठिन, लेकिन मानक समस्या है जिसे विभिन्न तरीकों से हल किया गया है। नमूना सी कोड

http://www.cs.princeton.edu/~rs/strings/

Sedgewick भी है:

एक दृष्टिकोण एक Trie यहाँ Sedgewick द्वारा preseted जैसे उपयोग करता है।

मैं शीर्षक बेंटले और Sedgewick द्वारा "छंटाई और स्ट्रिंग्स सर्च कर रहे हैं के लिए फास्ट एल्गोरिदम" कागज से बोली:

" '' के पास पड़ोसी 'के सवालों एक प्रश्न शब्द की दी गई आलोचनात्मक अंतर के भीतर सभी शब्दों का पता लगाने (उदाहरण के लिए, कोड सोडा से दूरी 2 है)। हम तारों में पड़ने वाले पड़ोसी के लिए एक नया एल्गोरिदम देते हैं, एक सरल सी कार्यान्वयन प्रस्तुत करते हैं, और इसकी दक्षता पर प्रयोगों का वर्णन करते हैं। "

इंडेक्सिंग का उपयोग करने का दूसरा दृष्टिकोण है। स्ट्रिंग को अक्षर एन-ग्राम्स और इंडेक्स में उलटा इंडेक्स (ल्यूसीन स्पेल चेकर के लिए Google यह देखने के लिए कि यह कैसे किया जाता है) में विभाजित करें। संभावित उम्मीदवारों को खींचने के लिए सूचकांक का उपयोग करें और फिर उम्मीदवारों पर हथौड़ा दूरी चलाएं या संपादित करें। यह सबसे अच्छा काम करने की गारंटी है (और अपेक्षाकृत सरल)।

भाषण मान्यता के क्षेत्र में एक तिहाई दिखाई देता है। वहां क्वेरी एक WAV सिग्नल है, और डेटाबेस तारों का एक सेट है। एक "टेबल" है जो सिग्नल के टुकड़ों से शब्दों के टुकड़ों से मेल खाती है। लक्ष्य सिग्नल करने के लिए शब्दों का सबसे अच्छा मिलान ढूंढना है। इस समस्या को शब्द संरेखण के रूप में जाना जाता है।

पोस्ट की गई समस्या में, डेटाबेस भागों में मिलान क्वेरी भागों की एक अंतर्निहित लागत है। उदाहरण के लिए किसी को हटाने/सम्मिलन/प्रतिस्थापन के लिए अलग-अलग लागत हो सकती है और यहां तक ​​कि मिस्चैचिंग के लिए अलग-अलग लागत "एफ" के साथ "एफ" कह सकती है।

भाषण मान्यता में मानक समाधान एक गतिशील प्रोग्रामिंग दृष्टिकोण का उपयोग करता है जो कि ह्यूरिस्टिक्स के माध्यम से प्रभावी होता है जो सीधे छंटनी करता है। इस तरह, केवल सर्वश्रेष्ठ, कहते हैं कि 50 उम्मीदवारों को रखा जाता है। इस प्रकार, नाम सबसे पहले खोज। सिद्धांत रूप में, आपको सबसे अच्छा मैच नहीं मिल सकता है, लेकिन आमतौर पर एक अच्छा मैच मिलता है।प्रत्यय Arrays और ए * पार्सिंग साथ

http://amta2010.amtaweb.org/AMTA/papers/2-02-KoehnSenellart.pdf

फास्ट लगभग स्ट्रिंग मिलान:

यहाँ बाद दृष्टिकोण के लिए एक संदर्भ है।

यह दृष्टिकोण शब्दों के लिए, लेकिन वाक्य को न केवल लागू होता है।

Answer 9

"सर्वश्रेष्ठ" विधि अपने इनपुट सेट और क्वेरी सेट के आधार पर काफी अलग अलग होंगे। एक निश्चित संदेश लंबाई होने से आप इस समस्या का वर्गीकरण संदर्भ में इलाज कर सकते हैं।

एक जानकारी सैद्धांतिक निर्णय वृक्ष एल्गोरिथ्म (C4.5 की तरह, उदाहरण के लिए) के प्रदर्शन पर सबसे अच्छा समग्र गारंटी प्रदान करेगा। इस विधि से इष्टतम प्रदर्शन प्राप्त करने के लिए, आपको पहले पारस्परिक जानकारी के आधार पर स्ट्रिंग इंडेक्स को सुविधाओं में क्लस्टर करना होगा। ध्यान दें कि आपको अंतिम शाखा में सभी पत्ते नोड्स को वापस करने के लिए वर्गीकरण को संशोधित करने की आवश्यकता होगी, फिर उनमें से प्रत्येक के लिए आंशिक संपादन दूरी की गणना करें। संपादन दूरी को केवल पेड़ के अंतिम विभाजन द्वारा दर्शाए गए फीचर सेट के लिए गणना की आवश्यकता है।

इस तकनीक का उपयोग करना, क्वेरी करने होना चाहिए ~ ओ (कश्मीर लॉग एन), k < < मीटर है, जहां कश्मीर सुविधा का आकार की उम्मीद है, मीटर स्ट्रिंग की लंबाई है, और n तुलना दृश्यों की संख्या है ।

इस पर प्रारंभिक सेटअप ओ (एम^2 + एन * टी^2), टी < मीटर, टी * के ~ मीटर से कम होने की गारंटी है, जहां टी किसी आइटम के लिए फीचर गिनती है। यह बहुत उचित है और किसी भी गंभीर हार्डवेयर की आवश्यकता नहीं है।

ये बहुत अच्छा प्रदर्शन संख्या तय मीटर बाधा की वजह से संभव नहीं है। का आनंद लें!

Answer 10

इस पुराने धागे

खोज करने के लिए जोड़ने से के लिए खेद है elementwise हे की एक जटिलता (एम * एन * एन) का मतलब होगा - Levenshtein दूरी की गणना के लिए खोज और हे (एन * एन) के लिए हे (एम) ।

ओपी छोटी से छोटी आलोचनात्मक दूरी (ग) को खोजने के लिए एक कारगर तरीका की तलाश में है, स्वयं स्ट्रिंग नहीं। यदि आपके पास सी (एक्स कहें) पर ऊपरी बाध्य है, तो आप ओ (लॉग (एक्स) * एम * एन) में सबसे छोटा सी पा सकते हैं।

स्टीफन के रूप में बताया, आप जल्दी से किसी दिए गए आलोचनात्मक दूरी के भीतर तार पा सकते हैं। यह पृष्ठ http://blog.faroo.com/2015/03/24/fast-approximate-string-matching-with-large-edit-distances/ प्रयासों का उपयोग करके इस तरह से एक तरह से बात करता है। 0 से एक्स 0