वाइल्डकार्ड के साथ फ़ाइल नाम खोज पैटर्न में टकराव की जांच

Question

मुझे फाइल सिस्टम वाइल्डकार्ड एक्सप्रेशन की तुलना करने की आवश्यकता है ताकि यह देखने के लिए कि उनके परिणाम ओवरलैप हो जाएं, केवल अभिव्यक्तियों की जांच/तुलना करके।

उदाहरण के लिए, हम एक उपयोगिता बना रहे हैं जो फ़ाइल सिस्टम वाइल्डकार्ड अभिव्यक्तियों के आधार पर फ़ाइलों को एक (या अधिक स्थानों) से अलग फ़ोल्डर में सॉर्ट करेगा। उदाहरण के लिए: * .txt फ़ोल्डर में जाता है, * .doc फ़ोल्डर बी में जाता है, और इसी तरह। वाइल्डकार्ड वर्ण जो हम समर्थन करेंगे * और?

मैं वाइल्डकार्ड अभिव्यक्तियों का विश्लेषण करने से निर्धारित करने में सक्षम होना चाहता हूं, चाहे वे संघर्ष/ओवरलैप हों।

उदाहरण के लिए

, अगर मैं निम्नलिखित भाव है:

 
*.x.y 
*.y 

वे संघर्ष करेंगे (ओवरलैप) क्योंकि दूसरी अभिव्यक्ति * .y * .x.y परिणाम भी शामिल होगा। (उदा। एएक्सई दोनों अभिव्यक्तियों से मेल खाते हैं)

मैं सभी अभिव्यक्तियों का उपयोग करके पेड़ की संरचना का निर्माण करके इस पर आ रहा हूं, यह समझते हुए कि अभिव्यक्ति संघर्ष होने पर पेड़ बनाने का बहुत ही असफल हो जाएगा।

 
For example: 
*.x 
a.b 
a.c 
b.d 

might create a tree like 

     +-*-.-x 
     | 
start +--+ 
     |  +-b 
     |  | 
     +-a-.-+-c 
     | 
     | 
     +-b-.-d 

अगर मैं पैटर्न b.x जोड़ने का प्रयास करते, पेड़ * .x मार्ग का अनुसरण सफल हो सकता है, और इस तरह का कहना है कि पैटर्न पहले से ही मौजूद है।

क्या मैं सही दिशा में जा रहा हूं? या इस पर हमला करने के लिए एक ज्ञात एल्गोरिदम है?

Answer 1

यह जांचने के लिए कि क्या दो वाइल्डकार्ड पैटर्न एक ही फ़ाइल नाम से मेल खाते हैं, आप इस समस्या को तुलना के ग्रिड बनाने के रूप में देख सकते हैं पात्रों के जोड़े के बीच, और फिर यह जांच कर लें कि क्या एक विकर्ण पथ मौजूद है या नहीं। नीचे दिए गए उदाहरण दिखाता है कि कैसे वाइल्डकार्ड पैटर्न ab?.c?? और a*bc.* संभव संघर्ष के लिए जाँच की जा सकती:

जब दो समान शाब्दिक वर्णों के बीच एक मैच पाया जाता है, तो आप अगले अक्षरों तक तिरछे ले जाने की जांच करने के। (हरा तीर से दर्शाया गया)

शाब्दिक वर्ण और एक एकल चरित्र वाइल्ड कार्ड ? सामना होता है, वहाँ दो संभावनाएं हैं जब: या तो वाइल्ड कार्ड वर्ण (तिरछे ले जाते हैं) से मेल खाता है, या वाइल्डकार्ड खाली जगह से मेल खाता है , और आप इसे छोड़ दें। (बैंगनी तीर के साथ दर्शाया गया है)

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

कोड उदाहरण 1 (पुनरावृत्ति)

नीचे एक सरल जावास्क्रिप्ट कार्यान्वयन जो ग्रिड तिरछे से अधिक दोहराता, निशान कोशिकाओं जहाँ से पहुंचा जा सकता है वर्तमान सेल, और तब जांचता है कि निचला दायां सेल पहुंच योग्य है या नहीं। कुछ उदाहरण देखने के लिए कोड स्निपेट चलाएं। (अद्यतन: ऊपर से नीचे बाएँ-से-दाएँ बजाय ठीक तिरछे करना होगा)

function wildConflict(wild1, wild2) { 
 
    var grid = [[true]], width = wild1.length, height = wild2.length; 
 
    for (var x = 1; x <= width; x++) grid[x] = []; 
 
    for (var y = 0; y < height; y++) { 
 
     for (var x = 0; x < width; x++) { 
 
      if (grid[x][y]) { 
 
       var a = wild1.charAt(x), b = wild2.charAt(y); 
 
       if (a == '*' || b == '*' || a == '?' || b == '?' || a == b) grid[x + 1][y + 1] = true; 
 
       if (a == '*' || b == '*' || a == '?') grid[x + 1][y] = true; 
 
       if (a == '*' || b == '*' || b == '?') grid[x][y + 1] = true; 
 
      } 
 
     } 
 
    } 
 
    return grid[width][height] == true; 
 
} 
 

 
var a = ["a", "a", "a*", "abc", "a*", "*.x.y", "*.x.y", "a*b*", "a*bc.*", "a?c.de"]; 
 
var b = ["a", "b", "abc", "a?", "*b", "*.y", "*.x", "a*c*", "ab?.c??", "ac.d??"]; 
 
for (var i in a) document.write("&quot;" + a[i] + "&quot; &harr; &quot;" + b[i] + "&quot; &rarr; " + wildConflict(a[i], b[i]) + "<BR>");

कोड उदाहरण 2 (पुनरावर्ती)

एक साधारण पुनरावर्ती कार्यान्वयन में संभावित रूप से कुछ वर्ण जोड़े को एक से अधिक बार जांचने की कमी है। इसे 2 डी-सरणी की आवश्यकता नहीं है, लेकिन रिकर्सन स्पष्ट रूप से स्मृति का भी उपयोग करते हैं।

ध्यान दें कि जब एक बहु-वर्णित जंगली कार्ड * का सामना करना पड़ता है, तो एल्गोरिदम केवल दो संभावनाओं के साथ दोहराता है: एक चरित्र पर कूदें, या दूसरे चरित्र पर कूदें; दोनों पात्रों पर कूदना (यानी जंगली कार्ड बिल्कुल एक चरित्र से मेल खाता है) अगले चरण में देखभाल की जाती है, जब जंगली कार्ड की तुलना अगले चरित्र से की जाती है।

function wildConflict(wild1, wild2) { 
 
    var w1 = wild1.split(''), w2 = wild2.split(''); 
 
    return conflict(0, 0); 
 

 
    function conflict(p1, p2) { 
 
     if (p1 == w1.length || p2 == w2.length) { 
 
      if ((p1 == w1.length && p2 == w2.length) 
 
      || (p1 == w1.length - 1 && (w1[p1] == '*' || w1[p1] == '?')) 
 
      || (p2 == w2.length - 1 && (w2[p2] == '*' || w2[p2] == '?'))) { 
 
       return true; 
 
      } 
 
      else return false;       // premature end 
 
     } 
 
     else if (w1[p1] == '*' || w2[p2] == '*' || (w1[p1] == '?' && w2[p2] == '?')) { 
 
      return conflict(p1 + 1, p2) || conflict(p1, p2 + 1); 
 
     } 
 
     else if (w1[p1] == '?') { 
 
      return conflict(p1 + 1, p2) || conflict(p1 + 1, p2 + 1); 
 
     } 
 
     else if (w2[p2] == '?') { 
 
      return conflict(p1, p2 + 1) || conflict(p1 + 1, p2 + 1); 
 
     } 
 
     else if (w1[p1] == w2[p2]) { 
 
      return conflict(p1 + 1, p2 + 1); 
 
     } 
 
     else return false;        // unequal literals 
 
    } 
 
} 
 

 
var x = ["a", "a", "a*", "abc", "a*", "*.x.y", "*.x.y", "a*b*", "a*bc.*", "a?c.de"]; 
 
var y = ["a", "b", "abc", "a?", "*b", "*.y", "*.x", "a*c*", "ab?.c??", "ac.d??"]; 
 
for (var i in x) document.write("&quot;" + x[i] + "&quot; &harr; &quot;" + y[i] + "&quot; &rarr; " + wildConflict(x[i], y[i]) + "<BR>");

Answer 2

प्रत्येक वाइल्डकार्ड अभिव्यक्ति को एक सीमित automaton में बदलें जो इससे मेल खाता है।

परिमित automatons के चौराहे की गणना करें।

डायनामिक प्रोग्रामिंग का उपयोग यह देखने के लिए करें कि छेड़छाड़ कभी मेल खा सकती है या नहीं।

यदि आप इन अवधारणाओं को नहीं पहचानते हैं, तो कुछ साल पहले इसे समझाने के प्रयास के लिए Algorithm for exclusion of numbers देखें। (उस बिंदु पर नियमित अभिव्यक्तियों के संग्रह से मेल खाने वाली चीजों की गणना करने के लिए, लेकिन सिद्धांत समान हैं।)

Answer 3

मुझे लगता है कि आप नियमित अभिव्यक्ति में पैटर्न बदल जाते हैं और फिर अगर वे eachother से मेल देखने के लिए सक्षम हो सकता है? यहां समाधान the rules for Directory.GetFiles on MSDN पर आधारित है - मुझे लगता है कि कुछ है इसके साथ गलत है लेकिन मुझे यकीन नहीं है कि क्या।

यहाँ एक बुनियादी कार्यान्वयन है

private bool Equivalent(string patternOne, string patternTwo) 
    { 
     // convert both patterns to regexes based on rules for Directory.GetFiles 
     var expressionOne = FilePatternToRegex(patternOne); 
     var expressionTwo = FilePatternToRegex(patternTwo); 

     // if either regex matches the opposite pattern, we've got a conflict 
     return expressionTwo.IsMatch(patternOne) || expressionOne.IsMatch(patternTwo); 
    } 

    Regex FilePatternToRegex(string pattern) 
    { 
     // separate extension and filename 
     var extension = Path.GetExtension(pattern); 
     var filename = Path.GetFileNameWithoutExtension(pattern); 

     // escape filename 
     filename = EscapeFilePattern(filename); 

     // 3 character extensions are a special case -- should be greedy eg xls matches xlsx 
     // extension.Length == 4 bc its dot AND 3 characters 
     if (extension.Length == 4 && !extension.Contains("*") && !extension.Contains("?")) 
     { 
      extension = extension + ".*"; 
     } 
     else 
     { 
      // all other extension lengths just get escaped like normal regexes 
      extension = EscapeFilePattern(extension); 
     } 

     // our final pattern should also only match at the string start/end 
     var finalPattern = "\\A" + filename + extension + "\\z"; 

     return new Regex(finalPattern); 
    } 

    string EscapeFilePattern(string pattern) 
    { 
     // escape star and question mark bc they are filepattern significant 
     pattern = pattern.Replace("*", "%S%").Replace("?", "%Q%"); 

     // escape all other special regex characters 
     pattern = Regex.Escape(pattern); 

     // turn star and question mark into their regex equivalents 
     pattern = pattern.Replace("%S%", ".+").Replace("%Q%", "."); 

     return pattern; 
    } 

संपादित: टिप्पणी में आगे की चर्चा के आधार पर, इस टूटी हुई है। कोड नमूना का उपयोग करके सबूत यह टूट गया है:

 var dir = new DirectoryInfo(Environment.CurrentDirectory).CreateSubdirectory(Guid.NewGuid().ToString()); 
     var path = Path.Combine(dir.FullName, "abc"); 

     File.WriteAllText(path, "*"); 

     // verify both patterns match our file 
     Assert.AreEqual(path, dir.GetFiles("a*c*")[0].FullName); 
     Assert.AreEqual(path, dir.GetFiles("a*b*")[0].FullName); 

     // current regex based solution thinks they are NOT equivalent 
     // when they are 
     Assert.IsFalse(Equivalent("a*c*", "a*b*"));