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

É 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.

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.

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.

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.

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".

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.)

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

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.

@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 ...

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

• Identificação de idioma no limite
• Aprendizagem provavelmente correta

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.

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.