के लिए डायनामिक एल्गोरिदम मैं एक ऑटो-सही प्रोग्राम लिख रहा हूं जो levenshtein distance का उपयोग को 64 वर्णकों से अधिक के वाक्यांशों के लिए 8000 शब्दों वाले विशिष्ट शब्दकोश के आधार पर करने के लिए करता है।टेक्स्ट ऑटो-सही
शब्दकोश प्रत्येक शब्द "शब्द word_frequency" पर प्रत्येक पंक्ति में शामिल है। मैं उन जोड़े को स्टोर करने के लिए डिक्शनरी एंटर्री ऑब्जेक्ट्स का उपयोग करता हूं। क्लास डिक्शनरी एंट्री में दो फ़ील्ड हैं: मान: शब्द स्ट्रिंग freq स्टोर करता है: आवृत्ति स्टोर को एक लिंक्डलिस्ट के रूप में संग्रहीत किया जाता है। मैं 64 वर्ण स्ट्रिंग stdin से पढ़ा। प्रसंस्करण से पहले मैं सभी रिक्त स्थान हटा देता हूं। "कोओ लेवेदर" -> "कूलवेदर" मैंने देखा कि प्रत्येक उपसर्ग के लिए लेवेनशेटिन दूरी की गणना करने की असर, लेवेनशेटिन गतिशील (विकिपीडिया उदाहरण देखें) द्वारा गणना की गई मैट्रिक्स की अंतिम पंक्ति में यह सभी उपसर्गों के लिए दूरी देता है ।
फ़ंक्शन लेव दूसरे पैरामीटर स्ट्रिंग से l.distance युक्त एक वेक्टर लौटाता है जिसमें पहले सभी उपसर्ग शामिल हैं।
मेरा मुद्दा यह है कि मुझे कुछ अतिरिक्त नियमों का सम्मान करना होगा: मिनट लेव। दूरी -> शब्दों की न्यूनतम संख्या -> अधिकतम आवृत्ति योग -> न्यूनतम शब्दावली यह समझाया जाएगा कि समाधान की कुल संख्या 1 से अधिक है, हम कम से कम शब्दों वाले शब्दों को लेते हैं। यदि अभी भी एक से अधिक हैं तो हम नियमों की सूची का पालन करते हैं।
गतिशील जो मैं आवेदन कर रहा हूं वह एक knapsack गतिशील के समान कुछ है। "गले में आरक्षित": मैं कैसे शब्द शासन की न्यूनतम संख्या (अधिकतम आवृत्ति एक बहुत समान है)
यहाँ मैं अब तक इनपुट/आउटपुट उदाहरण की कोशिश की है, जहां इस विफल रहता है लागू करने के लिए पता नहीं है जवाब इतना आरक्षित होना चाहिए, जो मैं प्राप्त करता हूं वह वास्तव में परोसा जाता है मैंने इस विधि को चुना है क्योंकि यह अधिक कुशल है। जावा के लिए समय सीमा 2 सेकंड है।
अपडेट: 7 अप्रैल। मुझे अपनी समस्या का समाधान मिला है, हालांकि सीपीयू समय बहुत बड़ा है इसलिए मुझे इसे अनुकूलित करने की आवश्यकता है। यह 2000 एमएस से अधिक नहीं होना चाहिए और वर्तमान में यह लगभग 6000 मीटर है। तो अब मेरा मुख्य फोकस इसे अनुकूलित कर रहा है।
public static String guess (String input, LinkedList<DictionarEntry> Dictionar){
String curent = new String();
String output = new String();
int costMatrix[][][] = new int [input.length()][8000][input.length()];
int index[] = new int[128];
int prev[]= new int[128];
int d[]=new int [128];
int freq[]= new int[128];
int wcount[]=new int[128];
String values[] = new String[128];
for (int i=0 ; i < 128 ; i++){
d[i]=127;
freq[i]=0;
wcount[i]=1;
values[i]="";
}
d[0]=0;
freq[0]=0;
for (int i = 0 ; i <input.length(); ++i){
curent=input.subSequence(i, input.length()).toString();
long start =System.currentTimeMillis();
for (int j = 0 ; j < Dictionar.size();++j){
costMatrix[i][j]=lev(Dictionar.get(j).value,curent);
for(int k=1;k<costMatrix[i][j].length;++k){
if(d[i]+costMatrix[i][j][k]<d[i+k]){
d[i+k]= d[i]+costMatrix[i][j][k];
values[i+k]=values[i]+Dictionar.get(j).value;
freq[i+k]=freq[i]+Dictionar.get(j).freq;
index[i+k]=j;
prev[i+k]=i;
wcount[i+k]=wcount[i]+1;
}
else if ((d[i]+costMatrix[i][j][k])==d[i+k])
if((wcount[i]+1) <wcount[i+k]){
values[i+k]=values[i]+Dictionar.get(j).value;
freq[i+k]=freq[i]+Dictionar.get(j).freq;
index[i+k]=j;
prev[i+k]=i;
wcount[i+k]=wcount[i]+1;
}
else if ((wcount[i]+1)==wcount[i+k])
if((freq[i]+Dictionar.get(j).freq)>freq[i+k]){
values[i+k]=values[i]+Dictionar.get(j).value;
freq[i+k]=freq[i]+Dictionar.get(j).freq;
index[i+k]=j;
prev[i+k]=i;
wcount[i+k]=wcount[i]+1;
}
else if ((freq[i]+Dictionar.get(j).freq)==freq[i+k]){
if((values[i]+Dictionar.get(j).value).compareTo(values[i+k])>0){
values[i+k]=values[i]+Dictionar.get(j).value;
freq[i+k]=freq[i]+Dictionar.get(j).freq;
index[i+k]=j;
prev[i+k]=i;
wcount[i+k]=wcount[i]+1;
}
}
}
}
long finished =System.currentTimeMillis();
System.out.println((finished-start));
output="";
}
int itr=input.length();
while(itr!=0){
output = Dictionar.get(index[itr]).value + " " + output;
itr=prev[itr];
}
return output;
}
मुझे नियमों को कैसे लागू करना चाहिए और कैसे (आदर्श रूप से मैट्रिक्स का उपयोग करने से अधिक कुशल तरीके से)?
मामले में कोई प्रश्न या मैं स्पष्ट नहीं कुछ कृपया
* "क्या मैं प्राप्त वास्तव में ऐसा कर रहे कार्य किया है" * [वैसा] बस स्पष्ट होना: 8000 शब्दों के अपने शब्दकोश है "तो "," फिर "," परोसा गया "और" आरक्षित "है लेकिन इसमें" कष्ट "नहीं है? – TacticalCoder
इतना आरक्षित सही जवाब होगा क्योंकि आरक्षित आरक्षित और इतने आरक्षित के बीच लेवेनशेटिन दूरी बराबर है (यदि आप रिक्त स्थान को अनदेखा करते हैं, जो मैं करता हूं) लेकिन आरक्षित उच्च आवृत्ति है। – pAndrei
क्या यह एक गतिशील अहंकार होना चाहिए? क्या आप मानक जावा मानचित्र, सेट इत्यादि का उपयोग कर सकते हैं? – Andrejs