맞춤법 검사기의 유전 알고리즘 구현

Question

텍스트 파일의 철자를 검사하고 오류 및 수정 사항을 출력하는 맞춤법 검사기를 구현하고 싶습니다. 파이썬을 사용하여 이것을 만들고 싶습니다.

하지만 중요한 것은 유전자 알고리즘을 사용하여 구현하고 싶다는 것입니다. 맞춤법 검사기의 유전 알고리즘을 어떻게 구현할 수 있습니까?

Answer 1

내 아이디어가 완벽하거나 최적이라고 생각하지 마십시오. 그러나이 경로를 선택하기에 좋은 출발점이 될 수 있습니다. 유전자 알고리즘은 맞춤법 검사기에서 최상의 선택이 아닐 수도 있습니다.

유전 알고리즘의 경우 시작 인구, 유전자를 "차세대"(교차), 확실한 돌연변이 생성 방법 및 전달 대상 선택 방법으로 전달해야합니다. 차세대 (일명 피트니스 기능)로 이와 함께 당신은 물론 코퍼스가 필요할 것입니다. 좋은 점이 있다면 dictionary.com API를 사용해 볼 수 있습니다 (한번도 사용한 적이 없습니다) http://www.programmableweb.com/api/dictionary.com.

초기 인구의 경우 시작 인구가 수천 개의 똑같은 단어 (예 : [ 'hello'] * 1000)가된다는 끔찍한 문제가 있습니다. 여기에서 당신은 단지 그것이 단어인지 아닌지를 검사 할 수 있습니다. 그렇다면 그것이 True 일 것입니다. 왜냐하면 문법 검사가 그들의 대 vs 대 엉덩이에 고통이 될 것이기 때문입니다.

시작하려면 다양성을 얻기 위해 돌연변이에 전적으로 의존해야하므로 초기 세대 인 경우 돌연변이를 일으키기 쉽고 다양성이 커지면 돌연변이 가능성이 줄어 듭니다. 돌연변이는 어딘가에 임의의 문자를 삽입하고, 어딘가에 문자를 제거하고, 어딘가에 문자를 변경하고, 둘 중 하나 이상을 수행 할 수 있습니다.

피트 니스 기능을 위해서는 최선의 방법은 시퀀스 정렬 알고리즘을 사용하는 것입니다. 참조 : http://en.wikipedia.org/wiki/Sequence_alignment. 정말로 진보하고자하는 경우 인구 집단의 각 단어에 대한 소리 나는 철자를 만들고 해당 단어가 코퍼스의 어떤 단어와도 일치하는지 확인하고이를 기반으로 점수를 늘립니다 (예 : 발음은 동일하지만). 나는 그것에 대해 아무것도 알지 못한다. 이 모든 것을 염두에두면 응용 프로그램이 끔찍하게 느려지므로 마음에 두십시오. 인구를 1000-2000 명으로 제한하는 것이 가장 좋습니다.

크로스 오버의 경우 샘플을 몇 개 가져와야합니다. (초기에는 룰렛을 사용하여 가장 적합한 것을 골라야하지만 이후에는 속도 목적으로 토너먼트를 사용할 수 있습니다). 다시 각 부모 사이의 서열 정렬을 사용하여 각 부모로부터 끌어낼 문자를 결정할 수 있습니다 (즉, soeed 대 s_eeo는 soeed, seed, seeo 또는 soeeo가 될 수 있습니다).

전문적인 솔루션으로 생각하지 말고 몇 분 안에 생각해보십시오.하지만 유전자 알고리즘을 사용하기로 결정한 경우 좋은 시작일 수 있습니다.