एक एल्गोरिद्म सामान्य संपादन

Question

मैं दो शब्द सूची मिल गया है, एक उदाहरण खोजने के लिए:

list 1 list 2 

foot fuut 
barj kijo 
foio fuau 
fuim fuami 
kwim kwami 
lnun lnun 
kizm kazm 

मैं

o → u # 1 and 3 
i → a # 3 and 7 
im → ami # 4 and 5 

को खोजने के लिए यह घटनाओं की राशि द्वारा आदेश दिया जाना चाहिए चाहते हैं, इसलिए मैं फ़िल्टर कर सकता हूं जो अक्सर प्रकट नहीं होते हैं।

सूचियों में वर्तमान में 35k शब्द शामिल हैं, गणना औसत सर्वर पर लगभग 6h लेनी चाहिए।

Answer 1

मेरा अंतिम समाधान mosesdecoder का उपयोग करना है। मैंने शब्दों को एकल वर्णों में विभाजित किया और उन्हें समानांतर कॉर्पस के रूप में उपयोग किया और निकाले गए मॉडल का उपयोग किया। मैंने सुर्सिलवन और वल्लडर की तुलना की।

export IRSTLM=$HOME/rumantsch/mosesdecoder/tools/irstlm 
export PATH=$PATH:$IRSTLM/bin 

rm -rf corpus giza.* model 
array=("sur" "val") 
for i in "${array[@]}"; do 
    cp "raw.$i" "splitted.$i" 
    sed -i 's/ /@/g' "splitted.$i" 
    sed -i 's/./& /g' "splitted.$i" 
    add-start-end.sh < "splitted.$i" > "compiled.$i" 
    build-lm.sh -i "compiled.$i" -t ./tmp -p -o "compiled.lm.$i" 
    compile-lm --text yes "compiled.lm.$i.gz" "compiled.arpa.$i" 
done 

../scripts/training/train-model.perl --first-step 1 --last-step 5 -root-dir . -corpus splitted -f sur -e val -lm 0:3:$PWD/compiled.arpa.sur -extract-options "--SentenceId" -external-bin-dir ../tools/bin/ 

$HOME/rumantsch/mosesdecoder/scripts/../bin/extract $HOME/rumantsch/mosesdecoder/rumantsch/splitted.val $HOME/rumantsch/mosesdecoder/rumantsch/splitted.sur $HOME/rumantsch/mosesdecoder/rumantsch/model/aligned.grow-diag-final $HOME/rumantsch/mosesdecoder/rumantsch/model/extract 7 --SentenceId --GZOutput 

zcat model/extract.sid.gz | awk -F '[ ][|][|][|][ ]' '$1!=$2{print $1, "|", $2}' | sort | uniq -c | sort -nr | head -n 10 > results 

Answer 2

आप संपादन दूरी एल्गोरिदम का उपयोग कर सकते हैं, उदाहरण के लिए, Levenshtein distance। सटीक संशोधन पंजीकृत करने के लिए एल्गोरिदम में कुछ मामूली परिवर्तन करना आवश्यक हो सकता है।

Answer 3

दूरी एल्गोरिदम संपादित करें और LCS विधि जैसे लेवेनशेटिन दूरी लाभकारी हैं। लेकिन इन तरीकों से आप एक शब्द को दूसरे शब्दों में बदलने के लिए उपयोग किए जाते हैं, आप यह पता लगा सकते हैं कि कम से कम परिवर्तनों के साथ एक शब्द को दूसरे शब्द में कैसे बदला जाए। लेकिन वे दो शब्दकोशों में न्यूनतम परिवर्तनों को खोजने के लिए उपयोगी नहीं हैं।

सबसे लंबे समय तक आम subsequence (LCS) समस्या सबसे लंबे समय तक परिणाम को सभी दृश्यों के लिए आम दृश्यों का एक सेट में मिल रहा है (अक्सर बस दो)। ध्यान दें कि बाद में एक सबस्ट्रिंग से अलग है, सबस्ट्रिंग बनाम बाद में देखें। यह क्लासिक कंप्यूटर साइंस समस्या है, डिफ जैसे फ़ाइल तुलना कार्यक्रमों का आधार है, और बायोइनफॉरमैटिक्स में अनुप्रयोग हैं।

, LCS या किसी अन्य तरीकों का उपयोग कर List1 में प्रत्येक शब्द के लिए करके, लगता है कि कैसे सूची 2. उदाहरण के लिए में एक-दूसरे से उस शब्द में परिवर्तन, पैर & पैरों के बीच: LCS = एफटी, अंतर = ऊ = > ee। आपको एक द्विपक्षीय ग्राफ बनाना चाहिए जो पहला भाग अंतर शब्दों से बना है, और दूसरा भाग सूची 1 से बना है। दूसरे भाग में प्रत्येक नोड पहले भाग में अपने संबंधित अंतर से जुड़ा हुआ है।

मुझे लगता है कि लंबाई की लंबाई और कुल भाग सीमित हैं।

हम इस समस्या को ग्राफ के साथ मॉडल कर सकते हैं। प्रत्येक नोड को एक नोड में असाइन करें। उदाहरण ई → i (जो एक परिवर्तन में से एक निर्धारित करता है) एक नोड के लिए लेबल है। उदाहरण के लिए, यदि रूप p → क्ष द्विपक्षीय ग्राफ और शब्दों की की प्रत्येक जोड़ी के लिए कुल अंतर में एक भाग के लिए निर्धारित है के आपरेशन के सभी को समान एक है और एज संग्रह को परिभाषित है कि एज uvV के शिखर U कनेक्ट करता है शब्द (यू) (दूसरे भाग में) सही शब्द बदलने के लिए वी के परिवर्तनों को बदलने के लिए। आपके पास पहले भाग में अधिकतम 25 * 26 नोड है (इस उदाहरण के लिए)। यदि आपके मामले में लंबाई> = 1, तो आपको एक सीमा निर्धारित करने की आवश्यकता है। मैं मानता हूं कि प्रत्येक शब्द में परिवर्तन का अधिकतम हिस्सा बराबर 3 है। और इसलिए हमारे पास पहले भाग में 3 * 35K अधिकतम नोड है। अब आप पहले भाग में नोड के सेट का चयन करके समस्या हल कर सकते हैं जिसे दूसरे भाग में अधिकतम शब्द शामिल किया जा सकता है (आपके चुने गए शब्द को सही करने के लिए शब्द परिवर्तन होना चाहिए)।

नोड के सेट को खोजने के लिए इस आलेख में न्यूनतम वर्टेक्स कट खोजें, ताकि वे आपका अनुरोध प्रदान कर सकें। और अच्छे उत्तर प्राप्त होने तक कट वर्टेक्स एल्गोरिदम को दोहराएं।

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

यह ग्राफ सिमुलेशन आपकी समस्या का समाधान कर सकता है। वर्तमान समस्या कथन के साथ, एल्गोरिदम की यह सीमाएं ठीक से काम करती हैं।

उदाहरण के लिए

:

1-हटाने नोड 4 क्योंकि यह केवल जुड़ा हुआ है:

यह इस ग्राफ में सीमा के लिए उदाहरण (आपरेशन भाग में सभी नोड को दूर वे 1 बढ़त हासिल है कि) है (nod), फिर नोड (नोड) 2 हटाएं- नोड 2 को हटाएं क्योंकि यह केवल (sghoul) से जुड़ा हुआ है, फिर नोड (sghoul) 3 को हटाएं- अब नोड 3 को हटा दें क्योंकि यह केवल (गौड) से जुड़ा हुआ है [sghoul अंतिम चरण हटा दिया गया है], तो नोड (गौड)

हटा दें

और अब आपके पास एक ऑपरेशन ओओ => ई है और आप इसे चुन सकते हैं।

मैं और अधिक सोचूंगा और इस पाठ को संपादित करने का प्रयास करूंगा।