È possibile per un computer "apprendere" un'espressione regolare con esempi forniti dall'utente?

Question

È possibile che un computer " impari " un'espressione regolare da esempi forniti dall'utente?

Per chiarire:

• Non non voglio imparare espressioni regolari.
• Voglio creare un programma che " impara " un'espressione regolare da esempi forniti in modo interattivo da un utente, magari selezionando parti da un testo o selezionando marcatori di inizio o fine.

È possibile? Esistono algoritmi, parole chiave, ecc. Per cui posso Google?

MODIFICA : grazie per le risposte, ma non sono interessato agli strumenti che forniscono questa funzione. Sto cercando informazioni teoriche, come documenti, tutorial, codice sorgente, nomi di algoritmi, quindi posso creare qualcosa per me.

Answer 1

Il libro Introduzione alla teoria dell'apprendimento computazionale contiene un algoritmo per l'apprendimento di automa finito. Poiché ogni linguaggio regolare equivale a un automa finito, è possibile apprendere alcune espressioni regolari da un programma. Kearns e Valiant mostrano alcuni casi in cui non è possibile apprendere un automa finito. Un problema correlato è apprendimento dei modelli di Markov nascosti , che sono automi probabilistici che possono descrivere un sequenza di caratteri. Nota che la maggior parte delle espressioni moderne "quotate" usato nei linguaggi di programmazione è in realtà più forte dei linguaggi normali e quindi a volte più difficile da imparare.

Answer 2

Si, è possibile, possiamo generare regex da esempi (testo - > estrazioni desiderate). Questo è uno strumento online funzionante che fa il lavoro: http://regex.inginf.units.it/

Lo strumento online Regex Generator ++ genera una regex dagli esempi forniti usando un algoritmo di ricerca GP. L'algoritmo GP è guidato da un fitness multi-obiettivo che porta a prestazioni più elevate e struttura della soluzione più semplice (Occam's Razor). Questo strumento è un'applicazione dimostrativa del Machine Lerning Lab, Università di Trieste (Università degli studi di Trieste). Guarda il video tutorial qui .

Questo è un progetto di ricerca in modo da poter leggere sugli algoritmi usati qui .

Ecco! :-)

Trovare una regex / soluzione significativa dagli esempi è possibile se e solo se gli esempi forniti descrivono bene il problema. Consideriamo questi esempi che descrivono un'attività di estrazione, stiamo cercando codici articolo particolari; gli esempi sono coppie di testo / estrazione:

"The product code il 467-345A" -> "467-345A"
"The item 789-345B is broken"  -> "789-345B"

Un ragazzo (umano), guardando gli esempi, può dire: "i codici oggetto sono cose come \ d ++ - 345 [AB] "

Quando il codice articolo è più permissivo ma non abbiamo fornito altri esempi, non abbiamo prove per comprendere bene il problema. Quando si applica la soluzione generata dall'uomo \ d ++ - 345 [AB] al testo seguente, non riesce:

"On the back of the item there is a code: 966-347Z"

Devi fornire altri esempi, al fine di descrivere meglio cos'è una partita e cosa non è una partita desiderata: --i.e:

"My phone is +39-128-3905 , and the phone product id is 966-347Z" -> "966-347Z"

Il numero di telefono non è un ID prodotto, questa potrebbe essere una prova importante.

Answer 3

Nessun programma per computer sarà mai in grado di generare un'espressione regolare significativa basata unicamente su un elenco di corrispondenze valide. Lascia che ti mostri perché.

Supponi di fornire gli esempi 111111 e 999999, nel caso in cui il computer generi:

1. Una regex che corrisponde esattamente a questi due esempi: (111111|999999)
2. Una regex che corrisponde a 6 cifre identiche (\d)\1{5}
3. Una regex che corrisponde a 6 e nove [19[{6}
4. Una regex corrispondente a 6 cifre \d{6}
5. Uno dei tre precedenti, con limiti di parole, ad es. \ b \ d {6} \ b
6. Uno dei primi tre, non preceduto o seguito da una cifra, ad es. (<?! \ D) \ d {6} (?! \ D)

Come puoi vedere, ci sono molti modi in cui gli esempi possono essere generalizzati in un'espressione regolare. L'unico modo per il computer di creare un'espressione regolare prevedibile è richiedere di elencare tutte le possibili corrispondenze. Quindi potrebbe generare un modello di ricerca che corrisponde esattamente a tali corrispondenze.

Se non si desidera elencare tutte le possibili corrispondenze, è necessaria una descrizione di livello superiore. Questo è esattamente ciò che le espressioni regolari sono progettate per fornire. Invece di fornire un lungo elenco di numeri a 6 cifre, devi semplicemente dire al programma di abbinare "ogni sei cifre". Nella sintassi delle espressioni regolari, questo diventa \ d {6}.

Qualsiasi metodo per fornire una descrizione di livello superiore flessibile quanto le espressioni regolari sarà anche complesso come le espressioni regolari. Tutti gli strumenti che RegexBuddy possono fare è per rendere più semplice la creazione e il test della descrizione di alto livello. Invece di utilizzare direttamente la sintassi delle espressioni regolari abbreviate, RegexBuddy consente di utilizzare semplici blocchi inglesi. Ma non può creare la descrizione di alto livello per te, dal momento che non può magicamente sapere quando dovrebbe generalizzare i tuoi esempi e quando non dovrebbe.

È certamente possibile creare uno strumento che utilizza testo di esempio insieme alle linee guida fornite dall'utente per generare un'espressione regolare. La parte difficile nella progettazione di tale strumento è come chiede all'utente le informazioni guida di cui ha bisogno, senza rendere lo strumento più difficile da imparare rispetto alle espressioni regolari stesse e senza limitare lo strumento a lavori regex comuni o a semplici espressioni regolari.

Answer 4

Sì, è certamente " possibile " ;; Ecco lo pseudo-codice:

string MakeRegexFromExamples(<listOfPosExamples>, <listOfNegExamples>)
{
   if HasIntersection(<listOfPosExamples>, <listOfNegExamples>)
     return <IntersectionError>

   string regex = "";
   foreach(string example in <listOfPosExamples>)
   {
      if(regex != "")
      {
         regex += "|";
      }
      regex += DoRegexEscaping(example);
   }
   regex = "^(" + regex + ")<*>quot;;

   // Ignore <listOfNegExamples>; they're excluded by definition

   return regex;
}

Il problema è che esiste un numero infinito di regex che corrisponderanno a un elenco di esempi. Questo codice fornisce la regex più semplice / più stupida del set, fondamentalmente corrispondente a qualsiasi cosa nella lista di esempi positivi (e nient'altro, incluso uno qualsiasi degli esempi negativi).

Suppongo che la vera sfida sarebbe quella di trovare la regex più breve che corrisponda a tutti gli esempi, ma anche in questo caso, l'utente dovrebbe fornire input molto buoni per assicurarsi che l'espressione risultante sia "quella giusta".

Answer 5

Credo che il termine sia "induzione". Vuoi indurre una grammatica regolare.

Non penso che sia possibile con una serie finita di esempi (positivi o negativi). Ma, se ricordo bene, si può fare se c'è un Oracle che può essere consultato. (Fondamentalmente dovresti lasciare che il programma faccia domande sì / no all'utente fino a quando non è stato contenuto.)

Answer 6

Potresti voler giocare un po 'con questo sito, è abbastanza bello e sembra che faccia qualcosa di simile a quello di cui stai parlando: http://txt2re.com

Answer 7

Esiste un linguaggio dedicato a problemi come questo, basato su prolog. Si chiama progol .

Come altri hanno già detto, l'idea di base è l'apprendimento induttivo, spesso chiamato ILP ( programmazione logica induttiva ) nei circoli AI.

Il secondo link è l'articolo wiki su ILP, che contiene molto materiale di origine utile se sei interessato a saperne di più sull'argomento.

Answer 8

@Yuval è corretto. Stai osservando la teoria dell'apprendimento computazionale o l'inferenza induttiva. & Quot;

La domanda è più complicata di quanto pensi, poiché la definizione di "impara" non è banale. Una definizione comune è che lo studente può sputare risposte ogni volta che vuole, ma alla fine, deve smettere di sputare risposte, o sputare sempre la stessa risposta. Ciò presuppone un numero infinito di input e non dà assolutamente nessuna garauntee su quando il programma prenderà la sua decisione. Inoltre, non puoi sapere quando ha preso la sua decisione perché potrebbe ancora produrre qualcosa di diverso in seguito.

Con questa definizione, sono abbastanza sicuro che le lingue normali siano apprendibili. Secondo altre definizioni, non tanto ...

Answer 9

Ho fatto alcune ricerche su Google e CiteSeer e ho trovato queste tecniche / documenti:

• Identificazione della lingua nel limite
• Apprendimento probabilmente approssimativamente corretto

Anche Dana Angluin " Imparare serie regolari da query e controesempi " sembra promettente, ma non sono riuscito a trovare una versione PS o PDF, cita solo articoli per seminari.

Sembra che questo sia un problema difficile anche a livello teorico.

Answer 10

Se è possibile per una persona imparare un'espressione regolare, allora è fondamentalmente possibile per un programma. Tuttavia, quel programma dovrà essere programmato correttamente per poter imparare. Fortunatamente questo è uno spazio logico abbastanza limitato, quindi non sarebbe così complesso come insegnare a un programma per essere in grado di vedere oggetti o qualcosa del genere.