일반 Windows 검색에서 사용하는 내용을 모르겠습니다. 그러나 파일 인덱싱을 한 번에 사용한 다음 빠른 검색을 위해 인덱스를 나중에 사용하는 기술이 있습니다 (예 : Windows 검색 4.0)가장 빠른 검색 기법/방법은 무엇입니까? (파일 검색의 컨텍스트에서)
이보다 빠른 검색을위한 다른 방법이 있습니까? 구현의 관점에서 자세히 설명해 주시겠습니까? 나는 유사한 검색 작업을 수행하는 검색 응용 프로그램을 구축한다고 가정
: 나를 이런 식으로 넣어 보자, 그것은 간단하게 이해할 수 있도록하기 위해
(나는 그것을 구현해야한다고 가정) 우리가 창문에서 사용하는 것.
제 질문은 이러한 응용 프로그램을 빌드하는 데 사용할 수있는 옵션/방법/접근 방법은 무엇입니까? (빠르게 기존의 것보다.하는)
는(기술의 이진 검색 나무 종류를 사용할 수 있습니까?)
게시판 및 접미어 배열과 같이 큰 코퍼스를 대상으로 전체 텍스트 검색을 수행하는 데는 기본적으로 두 가지 기술이 사용됩니다.
게시 목록은 (용어, document_id) 쌍의 목록이며 선택적으로 문서의 위치를 포함합니다. 용어를 정렬하거나 용어별로 해시하는 경우 효율적으로 검색 할 수있는 전체 텍스트 인덱스가 있습니다.
게시 목록을 작고, 액세스가 빠르고, 업데이트가 빠르고, 유연성이 뛰어나고, 정확도를 저하시키는 다양한 기술이 있습니다. Lucene은 아마도 현재 상용 가능한 게시 목록 기반의 텍스트 인덱서 일 수 있으며, 이전의 주석과는 달리 PDF, Microsoft Word 등에서 발견 된 텍스트를 색인 할 수 있습니다. 토마스 마이어 호퍼 (Thomas Maierhofer)가 연결 한 Lucene.net project은 꽤 합리적인 포트처럼 보입니다. 물론 자바 버전에서 진행되고있는 일의 최첨단에 조금 뒤떨어져 있습니다.
메모리보다 훨씬 큰 코퍼는 디스크에 게시 목록을 저장해야합니다. 간단한 바이너리 검색 트리를 사용하여 접근하는 것을 막습니다. 각각 10 만 단어의 문서가있는 경우 10 억 개의 게시물이 있습니다. 즉, 이진 검색 트리의 최소 깊이는 30입니다. 문제는 트리의 루트에서 리프까지의 경로에있는 30 개의 노드는 일반적으로 디스크의 다른 부분에 위치하므로 디스크는 한 번에 게시물을 찾기 위해 30 번 검색해야합니다! 그것은 약 2½ 초이며, 이것은 매우 느립니다.
그러나 "B-tree"라는 이진 트리 데이터 구조의 수정 된 버전이 있습니다. 은 일 수 있습니다. Lucene은 B-tree와 비슷한 간단한 데이터 구조를 사용하지만 대규모 업데이트를 훨씬 쉽게 지원합니다. 필자는 dumbfts project이라는 동일한 데이터 구조의 아주 간단한 버전을 작성했습니다.이 파일 구조는 Python의 몇 페이지에서 전자 메일에 대한 전체 텍스트 검색 엔진을 구현합니다. 나는 매일 그것을 사용하고, 자유 소프트웨어이고, 내가 사용하는 것에 꽤 잘 작동하지만 Lucene과 같은 세계적 수준의 검색 시스템은 아니다.
정확성을 희생하여 게시 목록을 작게 만드는 예로, Gigabytes 관리 책 (및 mg4j project)에는 "signed minimal perfect hash table"이라고하는 데이터 구조가 있습니다.이 구조는 실제로 색인 된 - 그냥 해시합니다. 따라서 거짓 긍정의 가능성은 매우 적습니다. 용어를 포함하고 있다고 가정하는 문서를 검색해야합니다.
훨씬 작고 약간 느린 기수 트리 (일명 시도)의 접미사 배열은 GLIMPSE 및 기타 몇 가지 프로그램에 의해 구현되지만 근본적으로 요즘 사용되지는 않습니다. 게시 목록 데이터 구조에는 일부 융통성이 없습니다. 예를 들어 철자가 틀린 정규 표현식 검색 및 검색을 허용하지만 빠른 것은 아닙니다. 접미사 배열을 기반으로하는 Burrows-Wheeler Transform의 최근 작업은 압축 된 파일 이 전체 텍스트 색인 인 인 압축 알고리즘을 제공합니다. 이 문서의 가장 잘 알려진 버전은 FM-index입니다. 이전 버전의이 기술은 아마도 발표되지 않았다고 들었지만 말입니다.위에 설명 된 다른 기술과는 달리, 문서가 PDF 파일이거나 이와 비슷한 경우에는 실제로 작동하지 않는다고 생각합니다. 각 페이지의 텍스트 버전을 추출하고 색인을 생성하는 것과 동일한 접근 방식을 사용할 수 있지만, 원본 문서를 압축하는 이점을 얻지 못합니다.
내 지인 Tim은 2003 년 블로그 게시물 on search에 대해 아주 훌륭한 입문 서적을 작성했는데, 여전히 꽤 훌륭합니다. 그것들은 (최근의 개발을 제외하고)이 것들을 훨씬 더 깊이 다룬다.
라비 : 당신이 찾고있는 정보입니까?
편집 : 내 서식을 수정 해 주셔서 감사합니다, 마틴!
+1. 이것은 OP (또는 다른 답변)가 OP가 시작하기에 충분하지 않은 것 같습니다. 나는 무엇이든 될 것을 의심합니다. 아주 잘 쓰여졌습니다. 그것이 도움이되지 않았다면, 그것이 적어도 나를 가르쳤다. –
감사합니다, Lieven! 나는 그가 그것을 게시 한 이후 OP가 그것을 읽지 않았다고 생각한다 - 그는 여기 또는 그의 질문에 대해 의견을 남기지 않았다. –
나는 불평하고있는 것처럼 들리는 것을 의미하지 않았다 - 나는 단지 당신이 이전의 코멘트가이 대답에 대한 응답이 아니기 때문에 그것이 "당신에게 충분했는지"에 대한 정보가 없다는 것을 의미했다. –
당신은 파일 이름을 찾고, 아니면 당신은뿐만 아니라 내용을보고 싶어? 어떤 언어로 이것을 구현하고 싶습니까?
파일 이름 만 찾는 경우 색인은 성능이 크게 향상되는 반면 찾고자하는 각 파일을 열어야하는 경우 색인은 색인을 생성하는 데 도움이됩니다 찾고있는 콘텐츠가 일 수있는 파일이 일 수 있습니다.
당신이보고있는 것을 발견 할 때까지 각 파일을 열어야합니다.
예. 콘텐츠도보고 싶습니다. 구현 부분에 대해 말하면 .net 프레임 워크가 선호됩니다. –
그럼 파일을 걷고, 각각 하나씩 열고 내용을 살펴 봐야합니다. 한 가지 방법은 색인에 태그를 추가하는 것입니다. 태그는 현재 파일이 속한 가장 중요한 카테고리를 알려주며,이를 통해 파일을 적절한 속도로 효과적으로 찾을 수 있습니다. 안부 – Atmocreations
Lucene을 살펴보십시오. 그것은 텍스트 (파일)에 대한 슈퍼 빠른 검색 라이브러리입니다. 사용할 수있는 Lucene.NET도 있습니다. 직접 구현하려는 경우 구현을위한 좋은 출발점이자 벤치 마크입니다.
토마스에게 고마움을 전합니다.하지만 Lucene은 텍스트 파일에만 적합하고 나머지는 충분하지 않은 것으로 보입니다. –
@Ravi : 해결책은 PDF, DOC 등의 파일에서 텍스트를 추출하고 추출 된 텍스트를 lucene에 제공하는 것입니다. –
정확히 Lucene in Action 서적에는 전체 섹션이 있습니다. –
전체 텍스트 검색 : 단어 사전이 있다고 가정하면 각 단어에 대해 단어가 포함 된 문서와 그 단어의 정확한 위치가 문서에 기록됩니다. 이를 전체 텍스트 색인이라고하며 부울 검색 및 정확한 구문 일치와 같은 작업을 수행 할 수 있습니다. 전체 텍스트 인덱싱은 수백만 개의 문서로 쉽게 확장 할 수 있으며 Windows Search 4.0이 일반적으로 사용하는 것입니다. 참조 항목 : Lucene 또는 Sphinx.
개념 검색 : 개념 검색을 사용하면 관련 단어 (또는 전체 문서)를 입력하고 입력 내용과 가장 유사한 문서를 반환 할 수 있습니다. 문서 모음을 기반으로 단어 사이의 의미 링크를 추론 할 수있는 개념 공간을 만듭니다. 이렇게하면 컴퓨터가 검색중인 개념을 "이해"하고 개념적으로 유사한 단어 및 구와 일치하므로 더 관련성 높은 검색 결과를 반환 할 수 있습니다. 이것이 엔터프라이즈 검색 및 eDiscovery 솔루션에서 일반적으로 사용하는 솔루션입니다. 개념 검색을 제공하는 제품에는 Engenium과 Autonomy가 있습니다.
메타 검색 : 콘텐츠를 직접 검색하는 대신 메타 데이터라고하는 콘텐츠에 대한 정보를 검색합니다. 메타 데이터에는 태그, 키워드, 작성자 이름, 타임 스탬프 등과 같은 것들이 포함될 수 있습니다. 예를 들어, 문서 작성 당시의 대략적인 날짜를 알고 있다면 검색 기준을 더 빠르게 좁히기 위해 검색 기준에 해당 메타 데이터를 포함시킬 수 있습니다 결과.
알다시피 검색에 접근하는 방법은 다양하며 다양한 유형의 데이터 구조가 있습니다. 당신이 내가 정교하기를 원하는 특정 지역이 있다면, 나는 당신을 위해 그것을 할 수 있습니다.
웹에서 사용할 수있는 전체 텍스트 검색에 대한 많은 연구 논문이 있으며 많은 소스 코드가 있습니다. 이들을 살펴보면 이진 탐색 트리를 사용하는 것이 현대 하드웨어에서 좋은 결과를 제공하지 않는다는 것을 알 수 있습니다. 이진 검색 트리는 다중 레벨 캐시가있는 최신 CPU에서 가능한 한 신속하지 않은 매우 구체적인 데이터 구조입니다. 빠른 데이터 구조는 2보다 팬이 더 많습니다.
또한이 문제는 (기수) 트라이에 더 적합합니다. 위키 피 디아를 참조하십시오.
아마 당신은 여러분의 필요에 PigeonRank™을 적용 할 수 있습니다 : 당신은 매우 빠르다 크 누스 - 모리스 - 프랫 또는 보이어 - 더 검색을 사용할 수 있으며, 인덱스가 필요하지 않습니다
.
그들은 당신의 코퍼스 크기에서 선형 시간입니다.15GiB 코퍼스가 있고 디스크가 초당 40MB를 읽을 수있는 경우 CPU가 디스크를 따라갈 수있을만큼 빠르다고 가정 할 때 검색 결과를 최소 6 분 동안 얻지 못합니다. 대조적으로, 나는 매일 15GB의 코퍼스에서 풀 텍스트 인덱스를 쿼리하고 몇 초 안에 결과를 얻는다. Google은 수십억 개의 웹 페이지에 전체 텍스트 색인을 제공하며 1 초 이내에 검색 결과를 제공 할 수 있습니다. –
우선, 직접 제작해야하는 이유가 무엇입니까? Lucene (그리고 .NET 용 NLucene)과 같은 좋은 오픈 소스 프로젝트가 있습니다.이 기능이 많이 내장되어 있습니다. 처음부터 다시 빌드해야하지 않는 한이 도구를 사용하십시오. 그렇게해도 프로젝트와 같은 소스에서 시작합니다. 정말 최고의 검색 기술은 하나도 없습니다. 내용물과 검색 내용에 따라 전체 가방이 있습니다. 자세한 내용을 알려주십시오. –
@ Anthony Anthony 감사합니다. 검색 응용 프로그램을 구현할 수있는 좋은 오픈 소스 프로젝트가 있다는 것을 알고 있습니다. 하지만 처음부터 다시 만들고 싶다고 가정 할 수 있습니다. 특별한 이유가 없습니다. 이전에 물어 보았던 것처럼 이진 검색 트리를 유용하게 사용할 수 있습니까? 나는 이것을 오래 전에 어딘가에서 읽었고 개념을 잊어 버렸기 때문에 이것을 말하고있다. 누군가가 도움을 주는지 우리에게 알려준다. –
Windows Search 4.0, Google 데스크톱 검색 등의 검색 기술은 내부적으로 색인 생성을 사용하고 B + 트리를 사용하며 현재 시장에 현재 존재하는 모든 데이터베이스에서 색인 생성에 주로 사용되므로 더 나은 답변을 얻을 것이라고 생각하지 않습니다. 그리고 정직하게 말하면, 색인 생성을 제외하고 색인 생성의 더 빠른 방법과 성능은 당신이 선택한 알고리즘에 달려 있습니다. –