주어진 텍스트 파일의 항목 목록이 큽니다.

Question

주어진 텍스트 파일의 항목 목록과 일치 시키려고합니다. 목록은 꽤 거대합니다. 이름이 하나 이상의 단어를 가질 수있는 조직 이름 목록입니다. 각 텍스트 파일은 여러 문단이있는 일종의 보통 글로서, 총 텍스트 수는 약 5000 단어입니다. 그것의 평범한 텍스트 콘텐츠, 그리고 거기에 내가 조직 이름을 찾을 수있는 분명한 경계가 없습니다.

목록의 모든 항목이 텍스트 파일에서 검색되고 일치하는 항목이 인식되고 태그 지정되는 방식을 찾고 있습니다.

이렇게 할 수있는 도구 나 프레임 워크가 있습니까?

나는 위키피디아에 나열된 모든 텍스트 마이닝 도구를 살펴 보았지만 아무도이 필요를 충족시키지 못했습니다.

모든 입력 사항을 높이 평가할 것입니다.

Answer 1

접근 1 : 유한 상태 기계

당신은 유한 상태 기계 (FSM)로 검색어를 결합 할 수 있습니다. 그런 다음 결과 FSM은 선형 시간에 모든 용어에 대한 문서를 동시에 스캔 할 수 있습니다. FSM은 각 문서에서 재사용 할 수 있기 때문에 문서를 작성하는 비용은 검색해야하는 모든 텍스트에 대해 상각됩니다.

좋은 정규 표현식 라이브러리는 FSM을 커버합니다. 자신 만의 코드를 작성하는 것은 아마도 스택 오버플로 (Stack Overflow) 대답의 범위를 벗어납니다.

기본 아이디어는 모든 검색어를 번갈아 사용하는 정규식으로 시작하는 것입니다. 조직 목록이 "cat"과 "dog"로 구성되어 있다고 가정합니다. 그것들을 cat|dog으로 합칠 것입니다. "핑크색 돼지"를 검색해야한다면 정규식은 cat|dog|pink pigs이됩니다.

정규 표현식에서 그래프를 작성할 수 있습니다. 그래프의 노드는 상태로, 방금 본 텍스트를 추적합니다. 그래프의 가장자리는 현재 상태와 입력의 다음 문자가 주어진 상태를 상태 머신에 알리는 전환입니다. 일부 주에서는 "최종"주라고 표시되어 있으며 그 중 하나에 도달 한 경우 귀하는 귀하의 조직 중 하나의 인스턴스를 발견했습니다.

가장 사소한 정규 표현식을 제외하고 그래프를 작성하는 것은 지루하고 계산이 비쌀 수 있으므로 이미 잘 수행 된 정규 표현식 라이브러리를 찾고 싶을 것입니다.

접근법 2 : 당신은 얼마나 많은 검색어에 따라, 시간

시 용어를 검색, 당신은 얼마나 많은 문서와 간단한 텍스트 검색 도구는 (아마도 하위 선형) 얼마나 빨리, 그것을 용어를 반복하고 각 용어에 대한 각 문서를 별도의 명령으로 검색하는 것이 가장 좋습니다. 확실히 이것은 가장 간단한 접근법입니다.

for doc in documents: 
    for term in search_terms: 
     search(term, doc) 

이 방법으로 루프를 중첩하면 디스크 캐시에 가장 친숙합니다.

이것이 일회성 작업 인 경우 취할 접근법입니다. 새 문서 (또는 다른 검색어 목록)를 계속 검색해야하는 경우 비용이 너무 많이들 수 있습니다.

접근 방법 3 : 접미사 트리 하나 개의 거대한 문서에

연결하여 모든 문서는, 정렬, 검색 조건을 접미사 트리를 구축하고, 일치를 찾고 접미사 트리를 통해 도보. 접미어 배열을 작성하고 사용하는 데 대한 대부분의 세부 정보는 Jon Bentley article from Dr. Dobb's에 있지만 다른 많은 리소스도 찾을 수 있습니다.

이 접근법은 메모리 집약적이며 대부분 캐시 친화적이며 따라서 매우 빠릅니다.

Answer 2

프리픽스 트리 일명 Trie를 사용하십시오.

모든 후보 이름을 접두사 트리에로드하십시오. 문서의 경우 트리와 일치시킵니다.

는 접두사 나무는 다음과 같이 대략 같습니다

는

{} 
+-> a 
| +-> ap 
| | +-> ... apple 
| +-> az 
|  +-> ... azure 
+-> b 
    +-> ba 
     +-> ... banana republic