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

Question

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

Para esclarecer:

• eu não querem aprender expressões regulares.
• Eu quero criar um programa que "aprende" uma expressão regular a partir de exemplos que são interativamente fornecido por um usuário, talvez por selecionar partes de um texto ou selecionando começar ou marcadores finais.

É possível? Existem algoritmos, palavras-chave, etc, que eu posso Google para?

Editar : Obrigado pelas respostas, mas eu não estou interessado em ferramentas que fornecer este recurso. Estou à procura de informações teóricas, como documentos, tutoriais, código fonte, nomes de algoritmos, para que eu possa criar algo para mim.

Answer 1

O livro Uma introdução à teoria da aprendizagem computacional contém um algoritmo para a aprendizagem de uma 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 mostrar alguns casos em que não é possível aprender um autômato finito. Um problema relacionado é aprendendo Modelo oculto de Markov , que são autômato probabilístico que podem descrever um sequência de caracteres. Note-se que a maioria dos modernos "expressões regulares" usados ??em linguagens de programação são realmente mais forte do que linguagens regulares e, portanto, às vezes mais difícil de aprender.

Answer 2

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

ferramenta online Regex Generator ++ gera um regex de exemplos fornecidos usando um algoritmo de busca GP. O algoritmo GP é impulsionado por uma aptidão multiobjective o que leva a um maior desempenho e mais simples estrutura de solução (Navalha de Occam). Esta ferramenta é um pedido demostrative pelo Lerning Lab máquina, Trieste Univeristy (Università degli Studi di Trieste). Por favor, olhe o vídeo tutorial aqui .

Este é um projeto de pesquisa para que você pode ler sobre usado algoritmos aqui .

Eis : -)

Encontrar um regex / solução significativa a partir de exemplos é possível se e só se os exemplos fornecidos descrevem bem o problema. Considere estes exemplos que descrevem uma tarefa de extração, nós estamos olhando para determinados códigos de item; os exemplos são de texto pares / Extração:

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

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

Quando o código do item é mais permissiva, mas não forneceu outros exemplos, não temos provas para entender bem o problema. Ao aplicar a solução humana gerada \ d ++ - 345 [AB] para o seguinte texto, ele falhar:

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

Você tem que fornecer outros exemplos, a fim de melhor descrever o que é um jogo e que não é um jogo desejado: --i.e:

"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 de produto, isso pode ser uma prova importante.

Answer 3

No programa de computador nunca vai ser capaz de gerar uma expressão regular significativa com base apenas em uma lista de jogos válidos. Deixe-me mostrar-lhe porquê.

Suponha que você fornecer os exemplos 111111 e 999999, deve o computador gerar:

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

Como você pode ver, há muitas maneiras em que exemplos podem ser generalizadas em uma expressão regular. A única maneira para o computador para construir uma expressão regular previsível é exigir-lhe a lista todas possíveis correspondências. Em seguida, ele poderia gerar um padrão de pesquisa que corresponda exatamente essas partidas.

Se você não deseja listar todos os jogos possíveis, você precisa de uma descrição de alto nível. Isso é exatamente o que as expressões regulares são projetados para fornecer. Em vez de fornecer uma longa lista de números de 6 dígitos, você simplesmente dizer ao programa para corresponder "quaisquer seis dígitos". Na sintaxe de expressão regular, isto torna-se \ d {6}.

Qualquer método de fornecer uma descrição de alto nível que é tão flexível como expressões regulares também vai ser tão complexo como expressões regulares. Todas as ferramentas como RegexBuddy pode fazer é torná-lo mais fácil de criar e testar a descrição de alto nível. Em vez de usar o concisa sintaxe de expressão regular diretamente, RegexBuddy permite a utilização de blocos de construção planície Inglês. Mas não pode criar a descrição de alto nível para você, uma vez que não pode magicamente sabe quando deve generalizar seus exemplos e quando não deveria.

É certamente possível para criar uma ferramenta que utiliza um texto de exemplo juntamente com orientações fornecidas pelo usuário para gerar uma expressão regular. A parte mais difícil na concepção de tal ferramenta um é como é que perguntar ao usuário as informações de orientação de que precisa, sem tornar a ferramenta mais difícil de aprender do que expressões regulares si mesmos, e sem restringir a ferramenta para trabalhos de regex comuns ou simples expressões regulares.

Answer 4

Sim, certamente é "possível"; Aqui está o pseudo-có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 irá corresponder uma lista de exemplos. Este código fornece o mais estúpido regex simples / no conjunto, basicamente combinando nada na lista de exemplos positivos (e nada mais, incluindo qualquer um dos exemplos negativos).

Eu suponho que o verdadeiro desafio seria encontrar o mais curto regex que corresponde todos os exemplos, mas mesmo assim, o usuário teria que fornecer muito bons entradas para garantir que a expressão resultante era "o caminho certo".

Answer 5

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

Eu não acho que isso é possível com um conjunto finito de exemplos (positiva ou negativa). Mas, se bem me lembro, isso pode ser feito se houver um Oracle que pode ser consultado. (Basicamente, você teria que deixar o programa perguntar o sim usuário / sem perguntas até que ele estava contente.)

Answer 6

Você pode querer brincar com este site um pouco, é bastante fresco e sons como ele faz algo semelhante ao que você está falando: http://txt2re.com

Answer 7

Há uma linguagem dedicada a problemas como este, com base no prólogo. É chamado Progol .

Como já foi mencionado, a idéia básica é a aprendizagem indutiva, muitas vezes chamado de ILP ( programação lógica indutiva ) nos círculos de IA.

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

Answer 8

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

A questão é mais complicada do que você pensa, como a definição de "aprender" não é trivial. Uma definição comum é que o aluno pode cuspir respostas sempre que quiser, mas, eventualmente, ele deve ou parada cuspir para fora respostas, ou sempre cuspir a mesma resposta. Isso pressupõe um número infinito de entradas, e dá absolutamente nenhuma garauntee quando o programa vai chegar a sua decisão. Além disso, você não pode dizer quando ele atingiu sua decisão porque pode ainda algo saída diferente depois.

Por esta definição, eu tenho certeza que as linguagens regulares são aprendida. Por outras definições, não tanto ...

Answer 9

Já fiz algumas pesquisas no Google e CiteSeer e encontrou estas técnicas / papéis:

• identificação Idioma no limite
• aprendizagem Provavelmente aproximadamente correta

Além disso Dana Angluin do "Aprender conjuntos regulares de consultas e contra" parece promissor, mas eu não era capaz de encontrar uma versão PS ou PDF, apenas a cita e apresentações dos seminários.

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

Answer 10

Se a sua possível para uma pessoa para aprender uma expressão regular, então é fundamentalmente possível para um programa. No entanto, esse programa terá de ser correctamente programado para ser capaz de aprender. Felizmente este é um espaço bastante finito de lógica, por isso não seria tão complexo como ensinar um programa para ser capaz de ver objetos ou algo parecido.