Controllo collisione negli schemi di ricerca dei nomi dei file con caratteri jolly

Question

Ho bisogno di confrontare le espressioni jolly del file system per vedere se i loro risultati si sovrappongono, solo esaminando/confrontando le espressioni.

Per esempio, stiamo costruendo un'utilità che ordina i file da uno (o più percorsi) in cartelle separate basate su espressioni jolly del file system. Ad esempio: * .txt va nella cartella a, * .doc va nella cartella b, e così via. I caratteri jolly che vorremmo supportare sarebbero * e?

Voglio essere in grado di determinare analizzando solo le espressioni jolly, se sarebbero in conflitto/si sovrappongono.

Per esempio, se ho le seguenti espressioni:

 
*.x.y 
*.y 

Essi sarebbero in conflitto (sovrapposizione), perché la seconda espressione * .y includerebbe risultati * .x.y. (ad esempio A.x.y corrisponderebbe a entrambe le espressioni)

Mi avvicino a questo costruendo una struttura ad albero usando l'utilizzo di tutte le espressioni, immaginando che l'atto stesso di costruire un albero fallirà se le espressioni contrastano.

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

might create a tree like 

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

Se provo ad aggiungere il b.x modello, l'albero sarebbe successo seguendo il percorso * .x, e quindi dire che il modello esiste già.

Sto andando nella direzione corretta? O c'è un algoritmo noto per attaccare questo?

Answer 1

Per verificare se due modelli di caratteri jolly possono corrispondere allo stesso nome file, è possibile considerare questo problema come creare una griglia di confronti tra coppie di caratteri e quindi verificare se esiste un percorso diagonale. L'illustrazione seguente mostra come modelli jolly ab?.c?? e a*bc.* può essere controllato per un possibile conflitto:

Quando viene trovata una corrispondenza tra due caratteri letterali identici, si muovono in diagonale per i prossimi personaggi da controllare. (indicato con la freccia verde)

Quando un carattere letterale e un singolo carattere è riscontrabile jolly ?, ci sono due possibilità: o il jolly corrisponde al carattere (muoversi diagonalmente), o il carattere jolly partite spazio vuoto e tu salti sopra. (indicate con frecce viola)

Quando viene rilevato un carattere jolly più caratteri *, tre possibilità devono essere presi in considerazione: il jolly corrisponde a uno spazio vuoto prima dell'altro carattere, il jolly corrisponde all'altra carattere, o la wild card corrisponde a più caratteri. (indicata con frecce blu)

esempio di codice 1 (iterativo)

Ecco un semplice implementazione JavaScript che itera griglia diagonale, segna cellule raggiungibili dal cella corrente e quindi controlla se la cella in basso a destra è raggiungibile. Esegui lo snippet di codice per vedere alcuni esempi. (aggiornamento: dall'alto verso il basso da sinistra a destra farà bene anziché diagonalmente)

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>");

codice di esempio 2 (ricorsivo)

Un semplice ricorsivo l'implementazione ha l'inconveniente di controllare potenzialmente alcune coppie di caratteri più di una volta. Non ha bisogno dell'array 2D, ma le ricors ovviamente usano anche la memoria.

Si noti che quando viene rilevata una wild card a più caratteri *, l'algoritmo ricorre con due sole possibilità: saltare sopra un carattere o saltare sopra l'altro carattere; saltare sopra entrambi i personaggi (ad esempio, la wild card corrisponde esattamente a un personaggio) viene preso in considerazione nel passaggio successivo, quando la wild card viene confrontata con il carattere successivo.

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

Trasforma ogni espressione di carattere jolly in un automa finito che lo abbini.

Calcolare l'intersezione degli automi finiti.

Utilizzare la programmazione dinamica per vedere se l'intersezione può mai corrispondere.

Se non si riconoscono questi concetti, vedere Algorithm for exclusion of numbers per un tentativo del mio di spiegarlo alcuni anni fa. (A quel punto per contare le cose che corrispondevano a una raccolta di espressioni regolari, ma i principi sono identici.)

Answer 3

penso che si potrebbe essere in grado di trasformare i modelli in espressioni regolari e poi vedere se corrispondono vicenda? La soluzione è basata su the rules for Directory.GetFiles on MSDN - Mi sembra che ci sia QUALCOSA in errore, ma non sono sicuro di cosa.

ecco un'implementazione di base

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; 
    } 

EDIT: sulla base di ulteriori discussioni nei commenti, questo è rotto. Prova utilizzando il codice di esempio che è rotto: