•  02-07-2019
  •  | 
  •  

문제

관련 콘텐츠를 검색하고 싶은 문서, 텍스트 파일이 너무 많습니다.아래 요구 사항에 설명된 대로 좋은 방법을 구현한 검색 도구를 본 적이 있는데 어디에 있는지 기억이 나지 않습니다.

내 요구 사항은 다음과 같습니다.

  • 최적화된 검색 기능이 필요합니다.나는 이 검색 기능에 공백으로 구분된 부분적으로 완전한(또는 완전한) 단어 목록(하나 이상)을 제공합니다.
  • 그런 다음 함수는 첫 번째 단어로 시작하거나 같은 단어를 포함하는 모든 문서를 찾은 다음 두 번째 단어를 사용하여 동일한 방식으로 찾은 문서를 검색합니다. 마지막에는 연결된 것으로 발견된 실제 단어가 포함된 목록을 반환합니다. 전체 단어 목록을 보려면 해당 단어가 포함된 문서(이름 및 위치)를 사용하세요.
  • 서류에는 다음이 포함되어야 합니다. 모두 목록에 있는 단어입니다.
  • 이 기능을 사용하여 입력한 대로 검색을 수행하여 결과를 트리형 구조로 실시간으로 표시하고 업데이트할 수 있도록 하고 싶습니다.

내가 생각해낸 해결책에 대한 가능한 접근 방식은 다음과 같습니다.세 개의 테이블이 있는 데이터베이스(대부분 mysql을 사용하여)를 만듭니다.'문서', '단어' 및 'Word_Docs'.

  • '문서'에는 모든 문서의 (idDoc, 이름, 위치)가 포함됩니다.
  • '단어'는 (idWord, Word) 를 가지며 모든 문서의 고유한 단어 목록입니다(특정 단어는 한 번만 나타납니다).
  • 'Word_Docs'에는 (idWord, idDoc)이 있으며 해당 단어가 나타나는 각 단어와 문서에 대한 고유한 ID 조합 목록이 됩니다.

그런 다음 키를 누를 때마다 편집 상자의 내용을 사용하여 함수가 호출됩니다(공백 제외).

  • 문자열이 토큰화되었습니다.
  • (여기서 내 바퀴가 약간 회전합니다):필요한 데이터 세트를 반환하기 위해 단일 SQL 문을 구성할 수 있다고 확신합니다.(실제_단어, 문서_이름, 문서_위치);(나는 SQL에 능숙하지 않습니다.) 또는 각 토큰에 대한 일련의 호출과 반복되지 않는 idDocs를 구문 분석합니까?
  • 그런 다음 이 데이터세트(/list/array)가 반환됩니다.

그러면 반환된 목록 콘텐츠가 표시됩니다.

예:다음을 사용하여 호출:"Seq STA COD"표시 :

sequence - start - code - Counting Sequences [file://docs/sample/con_seq.txt]
         - stop - code - Counting Sequences [file://docs/sample/con_seq.txt]
sequential - statement - code - SQL intro [file://somewhere/sql_intro.doc]

(등등)

이것이 최적의 방법입니까?함수는 빨라야 합니까, 아니면 공백이 있는 경우에만 호출해야 합니까?단어 완성 기능을 제공해야 합니까?(데이터베이스에 단어를 얻었습니다) 적어도 이것은 존재하지 않는 단어에 대한 쓸모없는 함수 호출을 방지할 것입니다.단어 완성인 경우:그건 어떻게 구현될까요?

(어쩌면 태그 검색을 위해 이러한 유형의 검색 솔루션을 사용할 수도 있을까요?(메인페이지 오른쪽 상단))

도움이 되었습니까?

해결책

당신이 말하는 것은 역 색인 또는 게시 목록을 게시하고 귀하가 제안한 내용 및 Mecki가 제안한 것에 대해 Similary를 운영합니다. 거꾸로 된 색인에 관한 많은 문헌이 있습니다. Wikipedia 기사는 시작하기에 좋은 곳입니다.

더 나은 것은 직접 구축하려고하는 대신 기존 거꾸로 된 색인 구현을 사용하십시오. MySQL과 최근 버전의 PostgreSQL에는 기본적으로 전체 텍스트 인덱싱이 있습니다. 당신은 또한 체크 아웃 할 수도 있습니다 루센 독립적 인 솔루션의 경우. 서면으로 고려해야 할 사항이 많이 있습니다. 좋은 토큰 화, 스템, 멀티 워드 쿼리 등을 포함한 역 지수와 사전 제작 된 솔루션 이이 모든 작업을 수행합니다.

다른 팁

가장 빠른 방법은 확실히 데이터베이스를 전혀 사용하지 않는 것입니다. 최적화된 데이터를 사용하여 수동으로 검색을 수행하면 선택 검색 성능을 쉽게 이길 수 있기 때문입니다.문서가 자주 변경되지 않는다고 가정할 때 가장 빠른 방법은 색인 파일을 작성하고 이를 사용하여 키워드를 찾는 것입니다.인덱스 파일은 다음과 같이 생성됩니다.

  1. 텍스트 파일에서 고유한 단어를 모두 찾습니다.이는 텍스트 파일을 공백으로 단어로 나누고 해당 목록에 이미 있는 경우를 제외하고 모든 단어를 목록에 추가하는 것입니다.

  2. 찾은 모든 단어를 알파벳순으로 정렬하세요.이를 수행하는 가장 빠른 방법은 다음을 사용하는 것입니다. 3방향 기수 QuickSort.이 알고리즘은 문자열을 정렬할 때 성능 면에서 이길 수 없습니다.

  3. 한 줄에 한 단어씩 정렬된 목록을 디스크에 씁니다.

  4. 이제 문서 파일을 검색하려면 완전히 무시하고 대신 인덱스 파일을 메모리에 로드한 다음 이진 검색을 사용하여 인덱스 파일에 단어가 있는지 확인하세요.크고 정렬된 목록을 검색할 때는 이진 검색을 이기기가 어렵습니다.

또는 단일 단계 내에서 단계 (1)과 단계 (2)를 병합할 수 있습니다.InsertionSort(이미 정렬된 목록에 새 요소를 삽입하기 위해 올바른 삽입 위치를 찾기 위해 이진 검색을 사용하는)를 사용하면 해당 단어가 이미 목록에 있는지 여부를 알아내는 빠른 알고리즘을 갖게 될 뿐만 아니라, 그렇지 않은 경우 삽입할 올바른 위치를 즉시 얻고 항상 새로운 위치를 삽입하는 경우 (3)단계에 도달하면 자동으로 정렬된 목록이 생성됩니다.

문제는 문서가 변경될 때마다 색인을 업데이트해야 한다는 것입니다...그러나 이는 데이터베이스 솔루션에도 적용되지 않을까요?반면에 데이터베이스 솔루션은 다음과 같은 몇 가지 이점을 제공합니다.문서에 너무 많은 단어가 포함되어 있어 색인 파일이 더 이상 메모리에 맞지 않더라도 이 기능을 사용할 수 있습니다(모든 영어 단어 목록도 일반 사용자 PC의 메모리에 들어갈 가능성은 낮습니다).그러나 엄청난 수의 문서에 대한 인덱스 파일을 로드해야 한다면 메모리가 문제가 될 수 있습니다.좋습니다. 영리한 트릭을 사용하여 이 문제를 해결할 수 있습니다(예:mmap 등을 사용하여 메모리에 매핑한 파일 내에서 직접 검색). 그러나 이는 데이터베이스가 빠른 조회를 수행하기 위해 이미 사용하는 것과 동일한 트릭이므로 휠을 다시 발명하는 이유는 무엇입니까?또한 문서가 변경되었을 때(즉, 데이터베이스가 잠금을 수행할 수 있거나 원자적 작업으로 업데이트 또는 업데이트를 수행할 수 있는 경우) 단어 검색과 색인 업데이트 사이의 잠금 문제를 방지할 수도 있습니다.목록 업데이트를 위한 AJAX 호출이 포함된 웹 솔루션의 경우 데이터베이스를 사용하는 것이 아마도 더 나은 솔루션일 것입니다(C와 같은 저수준 언어로 작성된 로컬에서 실행되는 애플리케이션인 경우 첫 번째 솔루션이 다소 적합합니다).

단일 선택 호출로 모든 작업을 수행하고 싶다면(최적은 아닐 수 있지만 AJAX를 사용하여 웹 콘텐츠를 동적으로 업데이트하면 일반적으로 두통을 최소화하는 솔루션임이 입증됨) 세 테이블을 모두 함께 JOIN해야 합니다.May SQL은 약간 녹슬었지만 시도해 보겠습니다.

SELECT COUNT(Document.idDoc) AS NumOfHits, Documents.Name AS Name, Documents.Location AS Location 
FROM Documents INNER JOIN Word_Docs ON Word_Docs.idDoc=Documents.idDoc 
INNER JOIN Words ON Words.idWord=Words_Docs.idWord
WHERE Words.Word IN ('Word1', 'Word2', 'Word3', ..., 'WordX')
GROUP BY Document.idDoc HAVING NumOfHits=X

좋아, 아마도 이것이 가장 빠른 선택이 아닐 수도 있습니다 ...더 빠르게 할 수 있을 것 같아요.어쨌든, 적어도 하나의 단어를 포함하는 일치하는 모든 문서를 찾은 다음 동일한 모든 문서를 ID별로 그룹화하고 함께 그룹화된 수를 세고 마지막으로 NumOfHits(IN 문에서 찾은 단어 수)가 있는 결과만 표시합니다. IN 문 내의 단어 수와 같습니다(10단어를 검색하면 X는 10입니다).

구문에 대해서는 확실하지 않습니다 (이것은 SQL Server 구문입니다).

-- N is the number of elements in the list

SELECT idDoc, COUNT(1)
FROM Word_Docs wd INNER JOIN Words w on w.idWord = wd.idWord
WHERE w.Word IN ('word1', ..., 'wordN')
GROUP BY wd.idDoc
HAVING COUNT(1) = N

즉, 좋아하지 않고. 같은 것들이 훨씬 더 복잡합니다.

Google 데스크탑 검색 또는 유사한 도구가 귀하의 요구 사항을 충족 할 수 있습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top