C# 메모리에서 텍스트 인덱스 구현

Question

성능에 민감한 작업이 있으며 메모리에 약 100,000 개 항목을 저장하는 것을 고려하고 있습니다. (ms SQL에서 지속되지만 복잡한 검색 성능을 향상시키기 위해 메모리에 복사)

키로 검색하여 텍스트를 검색 할 수 있습니다. 포함 상대적으로 느린 - 그것은 다음과 같이 각 쿼리 당 약 30ms의 소요 :

IEnumerable<Product> result = 
    products.Where(p => 
    p.Title.Contains(itemnames[rnd.Next(itemnames.Length)])); 

가 이미 메모리 데이터베이스 db4o는을 사용하려고하지만 성능이 더 악화입니다 - 검색 당 약 1.5 초 100K 항목에.

모든 개체 제목을 검토하지 않고 빨리 수행하기위한 옵션은 무엇입니까?

이 작업을 해결하는 데 사용할 수있는 메모리 데이터베이스는 무엇입니까?

Answer 1

제품이 저장된 데이터 구조를 변경할 수 있습니까? Contains 검색 속도를 높일 수있는 한 가지 방법은 가능한 모든 모든 Product.Title 부분 문자열을 Dictionary<string, List<Product>>에 저장하는 것입니다. 그러면 검색이 O (n) 대신 O (1)이됩니다.

당신은 너무 같은 모든 문자열 생성 할 수 있습니다

public static IEnumberable<string> AllSubstrings(this string value) 
{ 
    int index = 0; 
    while(++index <= value.Length) 
    { 
     yield return value.Substring(0, index); 
    } 

    index = 0; 
    while(++index <= value.Length - 1) 
    { 
     yield return value.Substring(index); 
    } 
} 

그런 다음 당신은 다음처럼 사전을 채울 수 있습니다 :

var titleIndex = new Dictionary<string, List<Product>>(); 

foreach(Product product in products) 
{ 
    foreach(string substring in product.Title.AllSubstrings()) 
    { 
     if(titleIndex.ContainsKey(substring)) 
     { 
      index[substring].Add(product); 
     } 
     else 
     { 
      index[substring] = new List<Product> { product }; 
     } 
    } 
} 

그리고 마지막을, 당신과 같이 검색을 수행

string searchString = itemnames[rnd.Next(itemnames.Length)]; 

if(titleIndex.ContainsKey(searchString)) 
{ 
    List<Product> searchResults = titleIndex[searchString]; 
} 

참고 : 짐작할 수 있듯이 이와 같은 r 데이터는 더 많은 CPU 시간을 필요로하며 더 많은 RAM을 사용합니다.

Answer 2

대신 SQL Server 전체 텍스트 검색을 사용해보십시오. http://msdn.microsoft.com/en-us/library/ms142571.aspx
예에서 순차 검색보다 빠를 수도 있습니다.

Answer 3

실제 포함 된 텍스트가 아닌 포함 된 단어를 실제로 검색해야하는 경우 메모리에 색인을 만듭니다. 사전을 작성하고 제목의 각 단어에 대한 항목을 사전에 추가하십시오. 그런 다음 개별 단어별로 빠른 조회를 수행 할 수 있습니다.

또 다른 옵션은 SQLite 메모리 내 데이터베이스에 데이터를로드하고 기본 제공 전체 텍스트 검색 엔진을 사용하여 검색을 수행하는 것입니다.

Answer 4

전체 텍스트 색인 (FTS3)이 포함되어 있으므로 SQLite를 사용해 보겠습니다.