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

Question

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

per chiarire:

• faccio non vogliono imparare le espressioni regolari.
• Voglio creare un programma che "impari" un'espressione regolare da esempi forniti in modo interattivo da un utente, magari selezionando parti da un testo o selezionando indicatori di inizio o fine.

È possibile? Ci sono algoritmi, parole chiave, ecc. Di cui posso occuparmi Google?

EDIT: Grazie per le risposte, ma io non sono interessato a strumenti che forniscono questa funzione. Sto cercando informazioni teoriche, come documenti, tutorial, codice sorgente, nomi di algoritmi, così posso creare qualcosa per me stesso.

Answer 1

Il libro An Introduction to Computational Learning Theory contiene un algoritmo per l'apprendimento di un automa finito. Poiché ogni lingua normale è equivalente a un automa finito, è possibile imparare alcune espressioni regolari da un programma. Kearns and Valiant mostrano alcuni casi in cui non è possibile imparare un automa finito. Un problema correlato è learning hidden Markov Models, che sono automi probabilistici che possono descrivere una sequenza di caratteri. Nota che la maggior parte delle "espressioni regolari" più moderne usate nei linguaggi di programmazione sono in realtà più forti dei linguaggi regolari, e quindi a volte più difficili da imparare.

Answer 2

si potrebbe desiderare di giocare con questo sito un po ', è abbastanza fresco e suona come fa qualcosa di simile a quello che si sta parlando: http://txt2re.com

Answer 3

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

Non penso sia possibile con un insieme finito 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 chieda all'utente sì/no domande finché non è stato contenuto.)

Answer 4

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

Answer 5

Sì, è certamente "possibile"; Ecco il 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 + ")$"; 

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

    return regex; 
} 

Il problema è che ci sono un numero infinito di regexs che corrispondono un elenco di esempi. Questo codice fornisce la regex più semplice/più stupida dell'insieme, praticamente corrispondente a qualsiasi cosa nella lista di esempi positivi (e nient'altro, inclusi gli esempi negativi).

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

Answer 6

@Yuval è corretto. Stai guardando la teoria dell'apprendimento computazionale o "inferenza induttiva"."

La domanda è più complicata di quanto si pensi, poiché la definizione di" apprendere "non è banale. Una definizione comune è che lo studente può sputare risposte quando vuole, ma alla fine, deve smettere di sputare risposte, o sputa sempre la stessa risposta, che presuppone un numero infinito di input e non dà assolutamente alcun risultato quando il programma raggiungerà la sua decisione. Inoltre, non puoi dire quando ha raggiunto la sua decisione perché potrebbe ancora emettere qualcosa di diverso dopo.

Secondo questa definizione, sono abbastanza sicuro che i linguaggi regolari sono apprendibile. In altre definizioni, non tanto ...

Answer 7

No progra del computer m sarà mai in grado di generare un'espressione regolare significativa basata solo in un elenco di corrispondenze valide. Lascia che ti mostri perché.

Supponiamo che fornisci gli esempi 111111 e 999999, dovrebbe il computer generare:

1. Una corrispondenza espressione regolare esattamente questi due esempi: (111111|999999)
2. Un'espressione regolare corrispondenza 6 cifre identiche (\d)\1{5}
3. Una regex corrispondenti 6 uni e nove [19]{6}
4. Un regex corrispondente a 6 cifre \d{6}
5. Qualsiasi sopra tre, 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 si può vedere, ci sono molti modi in cui esempi possono essere generalizzati in un'espressione regolare. L'unico modo per il computer di creare un'espressione regolare prevedibile consiste nel richiedere di elencare tutte le corrispondenze possibili. Quindi potrebbe generare un modello di ricerca che corrisponde esattamente a quelle corrispondenze.

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

Qualsiasi metodo per fornire una descrizione di livello superiore flessibile come le espressioni regolari sarà altrettanto complesso delle espressioni regolari. Tutti gli strumenti come RegexBuddy possono essere utili per semplificare la creazione e il test della descrizione di alto livello. Invece di usare direttamente la sintassi dell'espressione regolare, RegexBuddy ti permette di usare semplici blocchi di costruzione inglesi. Ma non può creare la descrizione di alto livello per te, dal momento che non può sapere magicamente quando dovrebbe generalizzare i tuoi esempi e quando non dovrebbe.

È certamente possibile creare uno strumento che utilizza un testo di esempio insieme alle linee guida fornite dall'utente per generare un'espressione regolare. La parte difficile nel progettare un tale strumento è come chiedere 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 ai normali lavori regex o alle semplici espressioni regolari.

Answer 8

C'è un linguaggio dedicato a problemi come questo, basato sul prologo. Si chiama progol.

Come altri hanno già menzionato, l'idea di base è l'apprendimento induttivo, spesso chiamato ILP (inductive logic programming) in ambienti di intelligenza artificiale.

Secondo link è l'articolo wiki su ILP, che contiene un sacco di materiale utile se sei interessato a saperne di più sull'argomento.

Answer 9

Ho fatto qualche ricerca su Google e CiteSeer e hanno trovato queste tecniche/documenti:

• Language identification in the limit
• Probably approximately correct learning

anche Dana Angluin di "Imparare set regolari da query e controesempi" sembra promettente, ma non sono riuscito a trovare una versione PS o PDF, solo cita e documenti di seminario.

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

Answer 10

Sì, è possibile, è possibile generare espressioni regolari da esempi (testo -> estrazioni desiderate). Questo è uno strumento online funzionante che svolge il lavoro: http://regex.inginf.units.it/

Regex Generator ++ strumento online genera una regex da esempi forniti utilizzando un algoritmo di ricerca GP. L'algoritmo GP è guidato da un fitness multiobiettivo che porta a prestazioni più elevate e una struttura della soluzione più semplice (il Rasoio di Occam). Questo strumento è un'applicazione dimostrativa del Machine Lerning Lab, Università degli Studi di Trieste. Si prega di guardare il video tutorial here.

Questo è un progetto di ricerca in modo da poter leggere sugli algoritmi utilizzati here.

Ecco! :-)

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

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

Un ragazzo (umana), guardando gli esempi, possono dire --ie: "i codici articolo 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 umana \ d ++ - 345 [AB] al seguente testo, non riesce:

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

È necessario fornire altri esempi, al fine di descrivere meglio ciò che è una partita e ciò che non è un partita desiderata: --ie:

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

Il numero di telefono non è un prodotto id, questo può essere una prova importante.