텍스트 처리 소개: Python으로 빠른 사전 만들기(4부)

double형 배열의 Python 구현 (3부)

지금까지 우리는 주로 이중 배열의 생성에 대해 이야기했습니다.
읽은 적이 있다면 어느 정도 검색의 이미지를 가지고 있을지도 모릅니다.
창조 이야기가 여전히 조금 어렵다면 "이중 배열 만들기"를 다시 읽어보십시오.
손을 움직여 이중 배열로 테이블을 채우십시오.

증분 검색에 대해 쓰고 싶은 내용은 다음과 같습니다.
설명을 위한 6개의 단어에서 "donchan"을 검색하는 동안 머리에서 두 번째 글자 "don"이 나오면 리프 노드를 찾을 수 있습니다.
Pyrthon의 dict와 같은 연관 배열에서 "donchan"과 "don"은 별도의 검색입니다.
double 배열을 포함하는 Trie 트리에서는 검색 키와 순방향 일치 부분 문자열 간의 일치 항목을 동시에 선택할 수도 있습니다.
트리는 나무의 가장 큰 강점입니다.

문장의 표제어와 일치하는 모든 문자열을 찾는 프로세스를 생각할 때,
dict를 사용하여 유사한 사전 검색을 만들면 문장의 모든 문자 위치에서 시작합니다
모든 길이의 부분 문자열을 만들고 각각에 대한 dict를 쿼리해야 합니다.
형량이 길수록 더 어려워 보입니다.
반면에 Trie 트리로 검색하려면 어떻게 해야 합니까?
문장에서 각 문자의 위치만 제공하면 됩니다.
해당 위치에서 시작하는 다양한 길이의 문자열이 있는 검색 키를 만드는 데 신경 쓸 필요가 없습니다.
또한 Trie 트리에서 더 이상 전환할 수 없는 경우 즉시 프로세스를 종료합니다.
dict 와 같은 검색을 위해 길고 쓸모없는 키를 사용하지도 않습니다.
그런 다음 한 프로세스를 통과하면 해당 시점까지 부분 문자열의 사전과 일치하는 모든 표제를 얻을 수 있습니다.

이제 double 배열을 만든 프로그램과 독립적으로 double 배열을 사용하는 프로그램을 작성해 보겠습니다.
이 경우 jupyter-notebook 은 하단 셀로 이동할 수 있기 때문에 쉽습니다.

이중 배열을 만드는 프로그램에는 다양한 수량 (변수)이 나타났습니다.
그러나 double 배열을 사용하는 경우 다음을 수행해야 합니다.
지정된 노드 위치의 기본 및 확인 값일 뿐입니다.
base 배열을 귀찮게 하거나 값을 얻기 위해 확인할 필요조차 없습니다.
파일을 읽고 바이너리에 직접 액세스해 보겠습니다.

사용된 프로그램에서 클래스를 만듭니다. DArray 클래스에는 네 가지 방법이 있습니다.

방법: __init__
세 개의 사전 파일을 읽고 멤버로 유지합니다.
그러나 character = > character ID의 대응은 c2code라는 dict에 보관됩니다.

방법: 베이스
노드 위치에서 기본 구성 요소를 반환하는 getter와 같은 메서드입니다.

방법: 확인
노드 위치에서 check 구성 요소를 반환하는 getter와 같은 메서드입니다.

방법: search_gen
double 배열에 대한 검색은 생성 시점의 노드 간 전환과 정확히 동일합니다.
차이점은 노드를 새로 만들지 않고 전환이 불가능한 경우 그대로 검색이 완료된다는 것입니다.
어떤 면에서는 double 배열을 만드는 것보다 더 간단한 알고리즘입니다.
이 방법은 작성하기 쉽기 때문에 생성기입니다.
호출할 때 목록으로 변환하거나 for 문 대신 씁니다.

메소드의 입력은 증분 검색(예: 하나의 전체 문장)을 수행하는 검색 키입니다
및 문자 ID 목록. 또한 의사 코드 같은 문장으로 작성하려고 노력할 것입니다.

DArray 클래스의 프로그램은 다음과 같습니다. 꽤 짧습니다.

[코드 예제 4]

double형 배열의 Python 구현 (4부)

이제 실제로 위의 DArray 클래스를 사용해 보겠습니다.
더 긴 위키백과 문서를 검색하여 위키백과 표제어 문자열이 얼마나 많은 조회수를 얻는지 확인하고 싶습니다.
위키백과는 스크래핑을 금지하고 있으니 빨리
브라우저에서 기사 목록의 기사를 열고 복사하여 붙여넣고 텍스트 파일로 저장합니다.

"긴 페이지 (위키백과)"
https://ja.wikipedia.org/wiki/ 스페셜: 긴 페이지

나는 "유럽에서의 교회와 국가 분리의 역사"를 선택하여 church.txt으로 저장했다.
500KB가 조금 안 되는 분량으로, 한 기사에 비해 상당히 긴 텍스트입니다.

기사 검색은 3단계 프로세스입니다.
(1) 파일의 줄을 읽고,
(2) 해당 줄의 문자열에서 각 문자 위치로 시작하는 부분 문자열을 만듭니다.
(3) 각 부분 문자열에 대해 증분 검색을 수행합니다.

generator로 검색 방법을 작성했으므로 여기에서도 각 단계를 generator로 만들어 보겠습니다.
다단계 생성기는 결과를 차례로 변수로 전달합니다.
통과 시점에는 실제 계산이 수행되지 않습니다 (지연 평가).

업스트림 생성기가 두 개의 변수를 함께 넣고 튜플 형태로 흐르기를 원한다고 가정합니다.
다운스트림 발전기에서 일부를 사용하려면 어떻게 해야 합니까?
다운스트림 생성기에서

이 경우 업스트림 생성기를 여러 번 호출한 모든 결과가 배열로 확장됩니다.
(무서워요!) ）
그런 다음 해당 배열을 두 요소 튜플에 전달하려고 시도하여 요소 개수 오류가 발생합니다.

따라서 이를 작동시키는 방법은 다운스트림 생성기에서 for 루프를 한 번 만드는 것입니다.
그 중 다음을 받으려고 노력해야 합니다.

실제로 프로그램을 보는 것이 더 빠를 수 있습니다.

[코드 예제 5] 및 [예제 결과 5]

이 기사에는 사전과 약 85,000개의 문자열 일치가 있었습니다.
메모리 사용량은 약 64MB였으며 Core i7에서 약 2초였습니다.
연관 배열의 딕셔너리로 같은 작업을 수행했을 때 약 20 초가 걸렸습니다.
dict 버전에서는 words.txt에서 dict를 만드는 데 필요한 시간이 핸디캡으로 제외되었습니다.
원래 Trie 트리는 고속 알고리즘이지만 double 배열은 특히 빠릅니다.
(↑ 이것은 이 한 줄에 있는 이 기사의 요약입니다)

마지막에 몇 가지 생각

이 프로그램을 개선하기 위한 과제에 대해 생각해 보십시오.
"시스템에 통합하려면 더 많은 오류 검사가 필요하지 않습니까?"
이야기도 있습니다만, 지금은 그 쪽은 그만두겠습니다.

"C++로 다시 쓰기"
"문자 단위 대신 UTF8 바이트를 처리하고 문자 코드 값을 그대로 사용하십시오."
어느 쪽도 어렵지 않으니, 신경이 쓰이는 분은 꼭 시험해 보세요.

"나무가 되는 패트리샤"
Patricia tree (radix trie / compact prefix tree)는 Trie 트리의 독창성 중 하나입니다.
이 기사의 설명 및 구현에서는 전환이 분기되지 않을 때 리프 노드를 압축했습니다.

Patricia 트리에서는 리프 노드에 관계없이 모든 노드가 압축되므로 분기와 단일 경로가 없습니다.
예를 들어, 설명에 사용되는 여섯 단어의 세계에서, "→ → 단어 끝"의 전환은 분기가없고 직선 경로이므로 하나로 결합 될 수 있습니다.
그런 다음 9 개의 노드가 필요합니다. 세어 보세요.

패트리샤 나무는 오랫동안 트리 나무를 압축하는 방법으로 매우 자주 사용되어 왔습니다.
어쩌면 그럴 수도 있지만 이중 배열에서도 일반적인 방법 인 것 같습니다.
그러나 더블 어레인지가 패트리샤 우드인 경우에는 큰 차이가 있습니다.
즉, 단일 경로를 조합한 결과 "모든 노드에는 여러 전환 대상이 있습니다".
이것은 double array의 빈 공간을 왼쪽에서 깔끔하게 채우기가 어렵다는 것을 의미합니다.

double 배열을 만들 때 여러 측면을 병렬로 처리할 수 없습니다.
한 번에 한 단계씩 순차적으로 처리해야 하기 때문에 채우기 문제로 해결하는 데 너무 많은 시간이 걸립니다.
반면에 노드를 생성할 때마다 가장 왼쪽 루트 위치에서 여유 공간을 찾고 있다면 프로세스가 점차 느려집니다.
그렇기 때문에 "일단 공간이 어느 정도 채워지면 그 분야에서 더 열심히 일하지 않습니다."
현실적인 접근 방식인 것 같습니다. 특정 지역의 모든 공석이 충원되지 않더라도 언젠가 또는 특정 조건 하에서,
전환 대상 후보를 찾기 시작하는 왼쪽 끝의 위치가 오른쪽으로 이동합니다.

사실, 이 기사의 프로그램을 만들 때 double array의 성장과 함께
우리는 빈 공간이 어떻게 될지 조사하면서 작업을 진행했습니다.
그 결과, 처리 중에 분기가 없는 많은 수의 전환이 발생합니다.
이러한 노드는 왼쪽에서 점점 더 많은 빈 공간을 채우는 것으로 나타났습니다.
결과적으로 double 배열을 만드는 것도 부드럽고 빠릅니다.
작업(또는 입력 데이터)에 따라 "분기 전환이 인력을 지배하는 경우"와 같이
이 기사가 빈 포지션을 업데이트하는 방식에 문제가 있을 수 있습니다.

이러한 이유로 이 기사에서는 패트리샤 나무를 다루지 않았습니다.
기회가 된다면 또 도전해 보고 싶습니다.

지금까지 파이썬으로 사전 조회 프로그램을 만들었습니다. 읽어 주셔서 감사합니다.

* 이 기사에 있는 프로그램은 자유롭게 편곡하여 사용하십시오.
그러나 그러한 불이익으로 인해 발생하는 불이익에 대해서는 책임을지지 않습니다.

1234코드