उपसर्ग जावा नियमित अभिव्यक्ति अनुकूलन

मैं नियमित अभिव्यक्ति, या शब्दकोशों के अनुकूलन के लिए एक सरल तरीके के बारे में बात करना चाहता हूं। मैंने कुछ परियोजनाएं देखीं, जो परिमित राज्य मशीनों को अनुकूलित करती हैं , पैकेज जो पाठ में शब्दकोश का त्वरित मार्कअप करते हैं , लेकिन सिर्फ शब्दकोश लेने के लिए और एक नियमित अभिव्यक्ति डालते हैं जो किसी भी नियमित अभिव्यक्ति इंजन को पारित किया जा सकता है - मैंने इसे अभी तक नहीं देखा है।

तो समस्या यह है कि शहरों का एक बड़ा शब्दकोश है और आपको पाठ में इन सभी वाक्यांशों को खोजने की आवश्यकता है। भोली दृष्टिकोण इन शब्दों को एक साथ गोंद करने के लिए है, या इसलिए यह अभिव्यक्ति प्राप्त की जाती है (शहर 1 | शहर 2 | शहर 7 | ... शहरएन)। ऐसी अभिव्यक्ति को संसाधित करते समय, एक साधारण एनडीए इंजन (जिसमें जेडीके सहित बहुमत) पाठ में प्रत्येक चरित्र के लिए कम से कम एन चेक करेगा, सबसे खराब स्थिति में (जब शब्द में अंतिम शब्द से शब्दकोश में सभी शब्दों से अलग होता है) चेक शब्दकोश में अक्षरों की संख्या के बराबर होंगे।
यह बुरा है, लेकिन बेहतर किया जा सकता है।
किसी भाषा की एक विशिष्ट संपत्ति अतिरेक है। इस मामले में, यह अक्षरों के अनुक्रम की पुनरावृत्ति है। यहां मैं सबसे सरल अनुकूलन विधि के बारे में बात करूंगा - उपसर्ग अनुकूलन।
यदि शब्द एक ही उपसर्ग से शुरू होते हैं, तो गणना किसी भी उपसर्ग के लिए एक बार की जाएगी। इसलिए हम अपने शब्दकोश के अनुसार Trie का निर्माण करते हैं, और फिर इसे एक नियमित अभिव्यक्ति स्ट्रिंग में परिवर्तित करते हैं।

वृक्ष वर्ग

class Node { char ch = START; List<Node> nodes = Lists.newArrayList(); void add(String str) { if (str.length() == 0) return; char chNew = str.charAt(0); for (Node n : nodes) { if (n.ch == chNew) { n.add(str.substring(1)); return; } } Node newNode = new Node(); newNode.ch = chNew; newNode.add(str.substring(1)); nodes.add(newNode); } String toRegexp() {...} } 

जैसा कि हम इसके मुख्य ऐड मेथड चेक को देखते हैं कि क्या इसके बच्चों के बीच पहला चरित्र है, यदि नहीं, तो यह इस चरित्र के साथ शुरू होने वाले उपशीर्षक को बनाता है और देता है।
इस प्रकार, इस संरचना में, किसी भी उपसर्ग को केवल एक बार (पेड़ के माध्यम से पथ) संग्रहीत किया जाता है और हमारी लाइनों में होने पर इसका पुन: उपयोग किया जाता है।

दूसरी विधि पेड़ को एक नियमित अभिव्यक्ति में परिवर्तित करती है।

  String toRegexp() { StringBuilder str = new StringBuilder(); if (ch == START) { } else if (ch == END) { } else { //convert special characters like {}[]. String newStr = escapeRegexp(String.valueOf(ch)); str.append(newStr); } if (nodes.size() > 1) { str.append("(?:"); for (Node n : nodes) { str.append(""); str.append(n.toRegexp()); str.append("|"); } str.setLength(str.length() - 1); str.append(')'); } else if (nodes.size() == 1) { str.append(nodes.get(0).toRegexp()); } return str.toString(); } } 

यहाँ काम कर कोड है

 public static String convertListToRegexp(final boolean useNonCapturingGroups, String... strs) { Arrays.sort(strs, new Comparator<String>() { public int compare(String o1, String o2) { int res = o2.length() - o1.length(); if (res != 0) { return res; } return o1.compareTo(o2); } }); Node root = new Node(); for (String str : strs) { root.add(str + "$"); } return root.toRegexp(); } 

और उदाहरण है

 //create array of your entries String[] examples = new String[]{"javvva", "javggaaa", "javajava", "adsasd", "adasddsa"}; //convert them to optimal regexp String optimizedRegexp = RegExpUtils.convertListToRegexp(true, examples); Assert.assertEquals("(?:ad(?:asddsa|sasd)|jav(?:ajava|ggaaa|vva))", optimizedRegexp); //check that it is works for(String s : examples) Assert.assertTrue(s.matches(optimizedRegexp));