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

É possível que um computador “aprenda” 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 “aprenda” uma expressão regular 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. pelos quais eu posso pesquisar o Google?

EDIT : Obrigado pelas respostas, mas eu não estou interessado em ferramentas que fornecem esse recurso. Estou procurando informações teóricas, como trabalhos, tutoriais, código-fonte, nomes de algoritmos, para 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 ocultos de Markov , que são autômatos probabilísticos que podem descrever uma sequência de caracteres. Observe que as “expressões regulares” mais modernas usadas nas linguagens de programação são, na verdade, mais fortes do que as linguagens regulares e, portanto, às vezes, mais difíceis de aprender.

Nenhum programa de computador será capaz de gerar uma expressão regular significativa baseada 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. Uma regex correspondente exatamente a esses dois exemplos: (111111|999999)
  2. Uma regex correspondente a 6 dígitos idênticos (\d)\1{5}
  3. Um regex que combina 6 e noves [19]{6}
  4. Uma regex correspondente a 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, (?

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

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

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

É certamente possível criar uma ferramenta que usa texto de amostra junto com as diretrizes fornecidas pelo usuário para gerar uma expressão regular. A parte difícil na criação de tal ferramenta é como ela pede ao usuário as informações que ele precisa, sem tornar a ferramenta mais difícil de aprender do que as expressões regulares, e sem restringir a ferramenta a trabalhos comuns regulares ou simples expressões regulares.

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

Regex Generator ++ ferramenta on-line gera um regex de exemplos fornecidos usando um algoritmo de busca GP. O algoritmo GP é impulsionado por uma aptidão multiobjective que leva a um desempenho mais alto e uma estrutura de solução mais simples (Occam’s Razor). Esta ferramenta é uma aplicação demonstrativa do Laboratório Machine Lerning, Universidade de Trieste (Università degli studi di Trieste). Por favor, olhe o tutorial em vídeo aqui .

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

Contemplar! 🙂

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

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

Um cara (humano), olhando para 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 texto a seguir, ela falhará:

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

Você precisa fornecer outros exemplos para descrever melhor o que é uma correspondência e o que não é uma correspondência desejada: –ie:

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

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

Sim, é certamente “possível”; Aqui está o pseudo-código:

 string MakeRegexFromExamples(, ) { if HasIntersection(, ) return  string regex = ""; foreach(string example in ) { if(regex != "") { regex += "|"; } regex += DoRegexEscaping(example); } regex = "^(" + regex + ")$"; // Ignore ; they're excluded by definition return regex; } 

O problema é que há um número infinito de regexs que corresponderão a uma lista de exemplos. Este código fornece o regex mais simples / estúpido no 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 o regex mais curto que corresponda a todos os exemplos, mas, mesmo assim, o usuário teria que fornecer inputs muito boas para garantir que a expressão resultante fosse “a correta”.

Eu acredito que o termo é “indução”. Você quer induzir uma gramática regular.

Eu 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 ao usuário, sim / não, até que fosse conteúdo).

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

Há uma linguagem dedicada a problemas como esse, baseada em prólogo. Chama-se progol .

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

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

@Yuval está correto. Você está olhando para a teoria da aprendizagem computacional, ou “inferência indutiva”.

A questão é mais complicada do que você pensa, já que a definição de “aprender” não é trivial. Uma definição comum é que o aluno pode citar as respostas sempre que quiser, mas, eventualmente, deve parar de responder ou sempre citar a mesma resposta. Isso pressupõe um número infinito de insumos e não dá absolutamente nenhuma garantia 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 depois.

Por essa definição, tenho certeza de que linguagens regulares são aprendidas. Por outras definições, não tanto …

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

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

Também “Aprender conjuntos regulares a partir de consultas e contra-exemplos” de Dana Angluin parece promissor, mas eu não consegui encontrar uma versão para PS ou PDF, apenas citações e artigos para seminários.

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, esse é um espaço razoavelmente finito de lógica, então não seria tão complexo quanto ensinar um programa a ver objects ou algo assim.