[regex] 컴퓨터가 사용자가 제공 한 예제를 통해 정규식을 “학습”할 수 있습니까?

Question 1

컴퓨터가 사용자가 제공 한 예제를 통해 정규식을 “학습”할 수 있습니까?

명확히하기 위해 :

정규식을 배우고 싶지 않습니다 .
텍스트에서 부분을 선택하거나 시작 또는 끝 마커를 선택하여 사용자가 대화 형으로 제공하는 예제에서 정규식을 “학습”하는 프로그램을 만들고 싶습니다.

가능할까요? Google에서 사용할 수있는 알고리즘, 키워드 등이 있습니까?

편집 : 답변 해 주셔서 감사하지만 이 기능 을 제공하는 도구에는 관심이 없습니다 . 논문, 튜토리얼, 소스 코드, 알고리즘 이름과 같은 이론적 정보를 찾고 있으므로 스스로 무언가를 만들 수 있습니다.

Question 2

책 An Introduction to Computational Learning Theory 에는 유한 오토 마톤을 학습하기위한 알고리즘이 포함되어 있습니다. 모든 정규 언어는 유한 오토 마톤과 동일하므로 프로그램을 통해 일부 정규 표현식을 학습 할 수 있습니다. Kearns와 Valiant 는 유한 오토마타를 배울 수없는 몇 가지 사례를 보여줍니다. 관련 문제는 문자 시퀀스를 설명 할 수있는 확률 적 자동 장치 인 숨겨진 마르코프 모델을 학습 하는 것입니다. 프로그래밍 언어에서 사용되는 대부분의 최신 “정규식”은 실제로 정규 언어보다 강력하므로 때때로 배우기가 더 어렵습니다.

Question 3

예, 가능합니다. 예제 (텍스트-> 원하는 추출)에서 정규식을 생성 할 수 있습니다. 이것은 작업을 수행하는 온라인 도구입니다. http://regex.inginf.units.it/

Regex Generator ++ 온라인 도구는 GP 검색 알고리즘을 사용하여 제공된 예제에서 정규식을 생성합니다. GP 알고리즘은 더 높은 성능과 더 단순한 솔루션 구조 (Occam ‘s Razor)로 이어지는 다목적 피트니스에 의해 구동됩니다. 이 도구는 Trieste Univeristy (Università degli studi di Trieste)의 Machine Lerning Lab에서 제공하는 데모 응용 프로그램입니다. 여기 비디오 튜토리얼을 보세요 .

이것은 연구 프로젝트이므로 여기에서 사용 된 알고리즘에 대해 읽을 수 있습니다. .

보다! 🙂

예제에서 의미있는 정규식 / 솔루션을 찾는 것은 제공된 예제가 문제를 잘 설명하는 경우에만 가능 합니다 . 추출 작업을 설명하는 다음 예를 고려하여 특정 항목 코드를 찾고 있습니다. 예는 텍스트 / 추출 쌍입니다.

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

예를 보면 (인간) 사람은 “항목 코드는 \ d ++-345 [AB]와 같은 것입니다.”라고 말할 수 있습니다.

항목 코드가 더 관대하지만 다른 예를 제공하지 않은 경우 문제를 잘 이해할 수있는 증거가 없습니다. 사람이 생성 한 솔루션 \ d ++-345 [AB]를 다음 텍스트에 적용하면 실패합니다.

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

일치하는 항목과 원하는 항목이 아닌 항목을 더 잘 설명하려면 다른 예를 제공해야합니다. –ie :

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

전화 번호는 제품 ID가 아니므로 중요한 증거가 될 수 있습니다.

Question 4

컴퓨터 프로그램은 전적으로 다음과 같은 의미있는 정규 표현식을 생성 할 수 없습니다. 유효한 일치 목록 . 그 이유를 보여 드리겠습니다.

컴퓨터가 다음을 생성하면 111111 및 999999 예제를 제공한다고 가정합니다.

이 두 가지 예와 정확히 일치하는 정규식 : (111111|999999)
6 개의 동일한 숫자와 일치하는 정규식 (\d)\1{5}
6 개의 1과 9가 일치하는 정규식 [19]{6}
6 자리 숫자와 일치하는 정규식 \d{6}
단어 경계가있는 위의 세 가지 중 하나, 예 : \b\d{6}\b
앞 또는 뒤에 숫자가없는 처음 세 개, 예 :
(?<!\d)\d{6}(?!\d)

보시다시피, 예제를 정규식으로 일반화 할 수있는 방법은 많습니다. 컴퓨터가 예측 가능한 정규식을 작성하는 유일한 방법은 가능한 모든 일치 항목을 나열하도록 요구하는 것 입니다. 그런 다음 정확히 일치하는 검색 패턴을 생성 할 수 있습니다.

가능한 모든 일치 항목을 나열하지 않으려면 더 높은 수준의 설명이 필요합니다. 이것이 바로 정규식이 제공하도록 설계된 것입니다. 6 자리 숫자의 긴 목록을 제공하는 대신 “6 자리 숫자”와 일치하도록 프로그램에 지시하면됩니다. 정규식 구문에서 이것은 \ d {6}가됩니다.

정규식만큼 유연한 고급 설명을 제공하는 모든 방법도 정규식만큼 복잡합니다. RegexBuddy 와 같은 모든 도구 는 높은 수준의 설명을 쉽게 만들고 테스트 할 수 있도록하는 것입니다. 간결한 정규식 구문을 직접 사용하는 대신 RegexBuddy를 사용하면 일반 영어 구성 요소를 사용할 수 있습니다. 그러나 언제 예제를 일반화해야하는지, 언제 일반화해야하는지 마술처럼 알 수 없기 때문에 높은 수준의 설명을 만들 수 없습니다.

정규 표현식을 생성하기 위해 사용자가 제공 한 지침과 함께 샘플 텍스트를 사용하는 도구를 만드는 것은 확실히 가능합니다. 이러한 도구를 설계 할 때 어려운 부분은 도구를 정규식 자체보다 배우기 어렵게 만들지 않고 도구를 일반적인 정규식 작업이나 간단한 정규식으로 제한하지 않고 필요한 안내 정보를 사용자에게 요청하는 방법입니다.

Question 5

예, 확실히 “가능”합니다. 다음은 의사 코드입니다.

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

문제는 예제 목록과 일치하는 정규식의 수가 무한하다는 것입니다. 이 코드는 세트에서 가장 단순하고 어리석은 정규식을 제공하며, 기본적으로 긍정적 인 예제 목록의 모든 항목과 일치합니다 (그리고 부정적인 예제를 포함하여 다른 항목은 없음).

진짜 도전은 모든 예제와 일치하는 가장 짧은 정규식을 찾는 것이라고 생각하지만, 그 후에도 사용자는 결과 표현식이 “올바른 것”인지 확인하기 위해 매우 좋은 입력을 제공해야합니다.

Question 6

나는 그 용어가 “유도”라고 믿는다. 정규 문법을 유도하고 싶습니다.

유한 한 예제 (긍정적 또는 부정적)로는 가능하지 않다고 생각합니다. 하지만 제대로 기억하면 상담 할 수있는 오라클이 있으면 할 수 있습니다. (기본적으로 프로그램이 콘텐츠가 될 때까지 사용자에게 예 / 아니오 질문을하도록해야합니다.)

Question 7

이 사이트를 약간 가지고 놀아보고 싶을 수도 있습니다. 매우 멋지고 당신이 말하는 것과 비슷한 일을하는 것처럼 들립니다 : http://txt2re.com

Question 8

프롤로그를 기반으로 이와 같은 문제에 전념하는 언어가 있습니다. 프로 골 이라고 합니다 .

다른 사람들이 언급했듯이 기본 아이디어는 종종 ILP ( 유도 논리 프로그래밍 AI 서클에서 ) 입니다.

두 번째 링크는 ILP에 관한 위키 문서로, 주제에 대해 더 많이 배우고 싶다면 유용한 소스 자료를 많이 포함하고 있습니다.