É possível para um computador “aprender” uma expressão regular por exemplos fornecidos pelo usuário?

94

É possível para um computador "aprender" uma expressão regular por exemplos fornecidos pelo usuário?

Esclarecer:

  • Eu não quero aprender expressões regulares.
  • Eu quero criar um programa que "aprende" uma expressão regular a partir de exemplos que são fornecidos interativamente por um usuário, talvez selecionando partes de um texto ou selecionando marcadores de início ou fim.

É possível? Existem algoritmos, palavras-chave, etc. que posso pesquisar no Google?

EDIT : Obrigado pelas respostas, mas não estou interessado em ferramentas que oferecem esse recurso. Procuro informações teóricas, como artigos, tutoriais, código-fonte, nomes de algoritmos, para poder criar algo para mim.

Daniel Rikowski
fonte
4
Estou surpreso que ninguém tenha mencionado Regex :: PreSuf
tripleee

Respostas:

44

O livro Uma introdução à teoria da aprendizagem computacional contém um algoritmo para aprender um autômato finito. Como toda linguagem regular é equivalente a um autômato finito, é possível aprender algumas expressões regulares por um programa. Kearns e Valiant mostram alguns casos em que não é possível aprender um autômato finito. Um problema relacionado é aprender modelos de Markov ocultos , que são autômatos probabilísticos que podem descrever uma sequência de caracteres. Observe que a maioria das "expressões regulares" modernas usadas em linguagens de programação são realmente mais fortes do que as linguagens regulares e, portanto, às vezes mais difíceis de aprender.

Yuval F
fonte
43

Sim, é possível, podemos gerar regexes a partir de exemplos (texto -> extrações desejadas). Esta é uma ferramenta online de trabalho que faz o seu trabalho: http://regex.inginf.units.it/

A ferramenta online Regex Generator ++ gera um regex a partir de exemplos fornecidos usando um algoritmo de pesquisa GP. O algoritmo GP é conduzido por uma aptidão multiobjetivo que leva a um desempenho superior e uma estrutura de solução mais simples (Navalha de Occam). Esta ferramenta é um aplicativo demonstrativo do Machine Lerning Lab, Trieste University (Università degli studi di Trieste). Por favor, veja o vídeo tutorial aqui .

Este é um projeto de pesquisa para que você possa ler sobre os algoritmos usados aqui .

Ver! :-)

Encontrar uma regex / solução significativa a partir de exemplos é possível se e somente se os exemplos fornecidos descrevem bem o problema. Considere esses exemplos que descrevem uma tarefa de extração, estamos procurando códigos de itens específicos; os exemplos são pares de texto / extração:

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

Um cara (humano), olhando os exemplos, pode dizer: "os códigos dos itens são coisas como \ d ++ - 345 [AB]"

Quando o código do item é mais permissivo, mas não fornecemos outros exemplos, não temos provas para entender bem o problema. Ao aplicar a solução gerada por humanos \ d ++ - 345 [AB] ao seguinte texto, ela falha:

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

Você deve fornecer outros exemplos, a fim de descrever melhor o que é uma correspondência e o que não é uma correspondência desejada: --ou:

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

O número de telefone não é uma identificação do produto, isso pode ser uma prova importante.

Fabiano Tarlao
fonte
4
Esta deve ser a melhor resposta. É possível, e isso o demonstra. A fonte está disponível aqui: github.com/MaLeLabTs/RegexGenerator
rjurney
Seu exemplo de códigos de produto ilustra por que essa pessoa deve procurar a especificação de códigos de produto e escrever a expressão regular com base na especificação, em vez de tentar inferir o regex de um conjunto limitado de códigos de produto de amostra (independentemente de ser uma pessoa ou um programa está tentando inferir o regex).
Jan Goyvaerts
2
Esta é a maneira certa de fazer as coisas. Meu exemplo é apenas uma forma de, conceitualmente, explicar o problema. Às vezes não há especificação ou o cara simplesmente não consegue escrever a expressão regular (falta de conhecimento) por conta própria.
Fabiano Tarlao
2
O artigo "Inferência de expressões regulares para Texto Extração de Exemplos" contém uma explicação detalhada do algoritmo machinelearning.inginf.units.it/publications/...
mimmuz
3
Este é um excelente projeto e uma fantástica demonstração do poder da programação genética, muito bem!
rcgeorge23
36

Nenhum programa de computador será capaz de gerar uma expressão regular significativa com base apenas em uma lista de correspondências válidas. Deixe me mostrar a você o porquê.

Suponha que você forneça os exemplos 111111 e 999999, caso o computador gere:

  1. Um regex que corresponde exatamente a esses dois exemplos: (111111|999999)
  2. Um regex correspondendo a 6 dígitos idênticos (\d)\1{5}
  3. Um regex correspondendo a 6 uns e noves [19]{6}
  4. Um regex que corresponda a qualquer 6 dígitos \d{6}
  5. Qualquer um dos três acima, com limites de palavras, por exemplo \b\d{6}\b
  6. Qualquer um dos três primeiros, não precedido ou seguido por um dígito, por exemplo (?<!\d)\d{6}(?!\d)

Como você pode ver, existem muitas maneiras pelas quais os exemplos podem ser generalizados em uma expressão regular. A única maneira de o computador construir uma expressão regular previsível é exigir que você liste todas as correspondências possíveis. Então, ele pode gerar um padrão de pesquisa que corresponda exatamente a essas correspondências.

Se você não deseja listar todas as correspondências possíveis, você precisa de uma descrição de nível superior. É exatamente para isso que as expressões regulares são projetadas. Em vez de fornecer uma longa lista de números de 6 dígitos, você simplesmente diz ao programa para corresponder a "quaisquer seis dígitos". Na sintaxe da expressão regular, torna-se \ d {6}.

Qualquer método de fornecer uma descrição de nível superior que seja tão flexível quanto as expressões regulares também será tão complexo quanto as expressões regulares. Todas as ferramentas como o RegexBuddy podem fazer é tornar mais fácil criar e testar a descrição de alto nível. Em vez de usar a sintaxe concisa da expressão regular diretamente, o RegexBuddy permite que você use blocos de construção em inglês simples. Mas ele não pode criar a descrição de alto nível para você, já que não pode saber magicamente quando deve generalizar seus exemplos e quando não deve.

Certamente é possível criar uma ferramenta que use um texto de amostra junto com as diretrizes fornecidas pelo usuário para gerar uma expressão regular. A parte difícil no projeto de tal ferramenta é como ela pede ao usuário as informações de orientação de que ele precisa, sem tornar a ferramenta mais difícil de aprender do que as próprias expressões regulares e sem restringir a ferramenta a trabalhos de regex comuns ou a expressões regulares simples.

Jan Goyvaerts
fonte
Você está certo, muitos algoritmos de aprendizado que encontrei após postar minha pergunta exigem informações positivas e negativas. Pelo que entendi, uma "descrição de nível superior" explícita não é necessária, porque o usuário a fornece respondendo a perguntas.
Daniel Rikowski,
Se uma ferramenta fizer perguntas, então a combinação das perguntas e das respostas dadas forma a descrição de nível superior. A qualidade dessas ferramentas depende muito das perguntas que ela faz.
Jan Goyvaerts,
Isso é estúpido porque se você forneceu outro exemplo, você pode eliminar algumas dessas possibilidades. Um outro exemplo elimina mais.
Cris
2
@Cris: O princípio permanece, independentemente de quantas amostras você forneça. Simplesmente muda as possibilidades. Por exemplo, adicionar 123456 altera # 2 a (\ d) \ 1 {5} | 123456 e # 3 a [19] {6} | 123456. Ou pode alterar o nº 3 para [1-69] {6}. Pode até ser que o padrão desejado corresponda a 6 dígitos idênticos ou 6 dígitos, onde cada dígito é um maior que o anterior. Mesmo se você fornecer 10.000 amostras de números de 6 dígitos, o programa não pode distinguir entre # 1, # 4, # 5 ou # 6 sem instruções extras do usuário.
Jan Goyvaerts,
Eu sinto que este problema é facilmente resolvido da seguinte maneira: O programa tenta ser o mais geral possível (dentro do razoável) e então dá exemplos de outras coisas que ele acha que combinariam. Simplesmente dizendo 'sim' e 'não' às correspondências propostas, você pode ajudá-lo a entender os limites do que você está realmente tentando capturar. Eu adoraria ver uma ferramenta em um editor de texto que usasse esse conceito e propusesse correspondências do arquivo aberto no momento.
Jon McClung
9

Sim, certamente é "possível"; Aqui está o pseudocódigo:

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

O problema é que há um número infinito de regexs que correspondem a uma lista de exemplos. Este código fornece a regex mais simples / estúpida do conjunto, basicamente correspondendo a qualquer coisa na lista de exemplos positivos (e nada mais, incluindo qualquer um dos exemplos negativos).

Suponho que o verdadeiro desafio seria encontrar a regex mais curta que corresponda a todos os exemplos, mas mesmo assim, o usuário teria que fornecer entradas muito boas para garantir que a expressão resultante fosse "a correta".

Daniel LeCheminant
fonte
3
Começa a ficar interessante quando o usuário insere amostras positivas e negativas . A regex teria que corresponder às amostras positivas e não às negativas.
user55400
1
@Thomas: O meu corresponde a todos os exemplos e nada mais!
Daniel LeCheminant
@blixtor - Na verdade, é bem fácil. Apenas não coloque nenhum dos exemplos negativos na regex construída, e eles serão rejeitados. Lembre-se de que aquele que o código constrói corresponde apenas a um exemplo positivo; exemplos negativos (e qualquer outra coisa) são excluídos por definição!
Daniel LeCheminant
Daniel está certo. Sem uma descrição de nível superior, uma lista de alternativas é tudo o que pode ser inferido de forma consistente e precisa a partir de uma lista de exemplos.
Jan Goyvaerts,
6

Acredito que o termo seja "indução". Você quer induzir uma gramática regular.

Não acho que seja possível com um conjunto finito de exemplos (positivos ou negativos). Mas, se bem me lembro, isso pode ser feito se houver um Oracle que possa ser consultado. (Basicamente, você teria que deixar o programa fazer perguntas sim / não ao usuário até que estivesse satisfeito.)

Jay Kominek
fonte
Sim, é isso que eu quero fazer, perguntar ao usuário de forma interativa.
Daniel Rikowski
As referências de Yuval F parecem ser o que eu tinha em mente, sugiro que dê uma olhada nelas.
Jay Kominek
5

Você pode querer brincar um pouco com este site, é muito legal e parece que faz algo semelhante ao que você está falando: http://txt2re.com

Chad Birch
fonte
4

Existe uma linguagem dedicada a problemas como este, baseada no prólogo. Chama-se progol .

Como outros mencionaram, a ideia básica é a aprendizagem indutiva, muitas vezes chamada de ILP ( programação lógica indutiva ) nos círculos de IA.

O segundo link é o artigo wiki sobre ILP, que contém uma grande quantidade de material fonte útil se você estiver interessado em aprender mais sobre o tópico.

patros
fonte
2

@Yuval está correto. Você está olhando para a teoria do aprendizado computacional, ou "inferência indutiva".

A questão é mais complicada do que você pensa, pois a definição de "aprender" não é trivial. Uma definição comum é que o aluno pode cuspir respostas sempre que quiser, mas, eventualmente, deve parar de cuspir respostas ou sempre cuspir a mesma resposta. Isso pressupõe um número infinito de entradas e não dá absolutamente nenhuma garantia de quando o programa chegará a sua decisão. Além disso, você não pode dizer quando chegou a sua decisão porque ainda pode produzir algo diferente mais tarde.

Por essa definição, tenho quase certeza de que as linguagens regulares podem ser aprendidas. Por outras definições, nem tanto ...

Brian Postow
fonte
2

Eu fiz algumas pesquisas no Google e CiteSeer e encontrei estas técnicas / artigos:

Além disso, "Aprendendo conjuntos regulares de consultas e contra-exemplos", de Dana Angluin, parece promissor, mas não consegui encontrar uma versão em PS ou PDF, apenas citações e artigos de seminário.

Parece que este é um problema complicado, mesmo no nível teórico.

Daniel Rikowski
fonte
0

Se é possível para uma pessoa aprender uma expressão regular, então é fundamentalmente possível para um programa. No entanto, esse programa precisará ser programado corretamente para poder aprender. Felizmente, este é um espaço razoavelmente finito de lógica, então não seria tão complexo quanto ensinar um programa a ser capaz de ver objetos ou algo parecido.

cjk
fonte
1
Não é verdade, você deve procurar problemas que são indecidíveis em máquinas de Turing.
Stephen Curial
Para ser justo, eu disse que se uma pessoa pode aprender um REGEX, uma máquina pode. Eu não estava falando isso geralmente.
cjk
@scurial Não creio que existam problemas comprovadamente solucionáveis ​​por pessoas, mas indecidíveis em máquinas de turing, existem?
Sunny88