텍스트 처리 소개: Python으로 빠른 사전 만들기(3부)
목차
[1부]
[2부]
[3부]
[4부]
double형 배열의 Python 구현 (1부)
위의 설명은 파이썬 프로그램 그대로입니다.
(여기에서 읽기 시작하고 내용이 궁금하다면 돌아가서 가볍게 읽어주세요.)
먼저 정책과 주의 사항을 적어두겠습니다.
"각 단계 처리"
이중 배열의 생성을 "한 노드에서 다음 노드로의 전환"이라고 합니다
그것은 측면의 처리로 나눌 수 있습니다.
우리는 모든 측면에서 그렇게 합니다.
한 측면을 처리하기 위해 어떤 종류의 입력이 필요한지 생각하면,
"표제어 앞에 오는 모든 문자열(빈 문자열과 표제어 자체 포함)의 경우,
한 문자의 다음 집합(단어의 끝 포함)이 먼저 필요합니다.
부분 문자열은 문자 ID 튜플로 표시되고 다음 문자는 문자 ID 집합으로 표시되며 dict에 저장됩니다.
이 기사에서는 이를 "분기 데이터베이스"라고 합니다.
다른 하나는 해당 시간에 전환되는 노드의 위치입니다.
즉, 부분 문자열의 시작에서 끝으로 전환될 때의 노드 위치입니다.
다시 말하지만, 부분 문자열의 문자 ID의 튜플이 키이고 전환 시점의 노드 위치가 값입니다.
dict(defaultdict)입니다. 이 기사에서는 이를 "전환 소스 데이터베이스"라고 합니다.
미리 분기 데이터베이스를 만들어 보겠습니다.
원본 데이터베이스의 항목은 double 배열을 만드는 동안 추가됩니다.
또한 항목에 해당하는 종횡비의 계산이 완료되면 더 이상 사용되지 않으므로 삭제하십시오.
"장점과 주의 사항"
그런데, "각 위상에 대해 처리하고 모든 위상에 대해 반복"하는 계산 방법에는 두 가지 장점이 있습니다.
첫 번째는 재귀를 사용할 필요가 없다는 것입니다.
재귀를 사용하여 구현하는 것이 더 쉽다고 생각하지만 너무 깊이 들어가지 않도록주의합니다.
런타임까지 그것에 대해 생각하기 어려울 수 있습니다.
반면에 재귀 없이 루프에 작성하려고 하면 일반적으로 알고리즘이 더 복잡해집니다.
이번에도 루프로 작성하려고 하는데, 이미 프로세스를 단계로 나누어 놓았기 때문에
그 후, 위상 수에 대해 간단한 루프를 수행하기 쉽기 때문에 쉽습니다.
또 다른 장점은 너비 우선 또는 깊이 우선과 같은 계산 순서가 프로그램 설계와 무관하다는 것입니다.
입력 데이터(분기 데이터베이스의 항목)의 검색 순서를 변경하면 둘 중 하나에 응답할 수 있습니다.
두 방법 중 하나로 계산할 수 있습니다. (이번에는 깊이를 우선시합니다)
좋은 것들로 가득 차 있지만 주의할 점이 있습니다. "전환을 계산할 때,
전이 전에 대한 계산은 이미 완료되었어야 합니다."
이는 소스 데이터베이스에 해당 순간에 소스 노드 위치가 필요하기 때문입니다.
분기된 데이터베이스를 준비할 때 이 점을 염두에 두십시오.
double형 배열의 Python 구현 (2부)
프로그램을 작성하고 이동하십시오. 먼저 입력 데이터(표제어 목록)를 준비해 보겠습니다.
표제어는 지금까지의 설명에서 익숙한 6 개의 단어 인 "den"과 "where"가 될 수 있습니다.
처음에 썼듯이 일본어 버전의 위키백과 제목 목록을 사용하겠습니다.
거의 모든 문자가 자체적으로 제목에 포함되므로 두 개 이상의 문자가 있는 제목을 사용하십시오.
이 기사를 작성하는 시점(2018년 10월)에는 약 180만 대가 있습니다. 그것은 완벽한 양입니다.
words.txt로 다시 저장하십시오. 표제어의 단어 ID는 줄 번호여야 합니다.
(만약 그것이 실제 사전이라면, 그것은 기록적인 수의 의미론적 데이터 등이 될 것입니다.)
가공을 넣어 주세요. 타이틀을 다운로드하려면 링크를 표시하므로 수동으로 수행하십시오.
이제 double 배열을 만드는 데 필요한 함수를 작성해 보겠습니다.
기능: get_branch_db
먼저 분기 데이터베이스를 준비하는 함수입니다. 다시
"Substring from the beginning" = > "다음 문자"가 dict에 등록됩니다.
그건 그렇고, 캐릭터에 ID를 할당하는 프로세스도 수행합니다. 또한 위의 참고 사항에 설명된 순서를 충족하는지 확인하십시오.
그건 그렇고, 나는이 과정에 defaultdict 를 사용하고 키가 등록 된 순서를 유지하고 싶다.
Python의 일부 버전 및 구현은 이 동작을 보장하지 않습니다.
새 클래스와 같은 dict를 만드는 것이 좋지만 현재로서는 간단하고 순진한 해결책은
dict와 별도로 키 배열을 만들어 보겠습니다.
기능: get_base_s
위치 s에서 전이할 때 밑변을 찾는 함수를 만듭니다.
분기 문자의 문자 ID 배열의 각 요소에서 가장 작은 문자 ID를 뺀 오프셋 배열을 만듭니다.
오프셋 배열의 각 요소가 사용되지 않는 영역의 가능한 한 왼쪽에 있도록 위치를 찾습니다.
거기에서 거꾸로 작업하면 밑을 찾을 수 있습니다.
기능: update_slot_start
이상과 관련하여, 환승 목적지를 결정하기 위해 빈방을 찾을 때, 매번 루트를 찾고 있다면,
노드 수가 증가함에 따라 점점 느려집니다.
double array의 빈 자리는 왼쪽부터 채워져야 하므로 빈 자리의 왼쪽 끝을 찾는 함수를 만듭니다.
그에 따라 부르자.
기능: make_darray
이것은 이중 배열 (base, check)을 만드는 함수입니다. 함수의 입력은 분기된 데이터베이스입니다.
의사 코드와 같은 문장으로 알고리즘을 작성해 보겠습니다.
__Empty 소스 데이터베이스(부분 문자열=>노드 위치)
분기 데이터베이스(루프)에서 한 쌍의 "substrings and the character set of the transition destination"을 __Retrieving.
자유 위치의 왼쪽 가장자리를 ____Update(update_slot_start)
______ 초기 계산(경로에서 전환):
________ 전환 소스S = 1
________ 전환 처리(다음 내용과 기본 사항이 동일하기 때문에 생략)
________ 전환 소스 데이터베이스에 전환 대상의 위치를 등록합니다.
______그렇지 않으면:
＿＿＿＿＿＿＿＿s의 값은 소스 데이터베이스에서 가져옵니다
리프 노드가 ________ 분기되지 않는 경우:
＿＿＿＿＿＿＿＿＿＿베이스[들]표제아이디을 음수로 설정합니다
다른 경우에는 다음과 같이 ________.
__________ 전환 대상(루프)의 문자 집합에서 한 문자 검색Retrieve one character from the character set of the transition destination (loop)
＿＿＿＿＿＿＿＿＿＿＿＿베이스[들]찾다(get_base_s)
____________ 전환 대상t = 밑변[s] + c
＿＿＿＿＿＿＿＿＿＿＿＿체크[t] = s
대상이 리프 노드인 경우 ____________:
＿＿＿＿＿＿＿＿＿＿＿＿＿＿밑바닥[t]표제아이디을 음수로 설정합니다
____________ 이외:
______________ 전환 소스 데이터베이스에서 전환 대상의 위치를 등록합니다.
________ 계산된 항목은 전환 원본 데이터베이스에서 삭제됩니다.
기능: save_darray
생성된 double 배열을 파일에 씁니다.
당분간은 배열의 요소당 3바이트를 남겨 둡니다.
(원래 그런 결정은 좋지 않으니 계산을 해 봅시다!) ）
pack이나 unpack을 사용하지 않고 바이너리를 처리하는 데 유용한 함수가 있으므로 여기에 맡기겠습니다.
또한 문자와 문자 ID 간의 대응 테이블은 문자열 형태로 텍스트 파일에 출력됩니다.
마지막으로, 위의 처리에 대한 호출은 main 함수에 요약되어 있습니다.
코드는 다음과 같습니다.
darray입니다. 세 개의 파일 {base,check,code}를 받았습니까?
약 770만 개의 노드가 생성되었습니다.
CPU가 Core i7이고 메모리가 8GB인 경우 처리하는 데 1~2분 정도 소요됩니다.
이제 이 이중 배열을 마무리 터치로 사용하는 검색을 고려해 보겠습니다.
하테부
