DawgSharp 다운로드 - DawgSharp 소스 코드 다운로드

DawgSharp

기타 소스코드

1.0.0

다운로드

[NuGet 패키지] [상용 라이선스 받기]

C#의 영리한 문자열 사전인 DawgSharp

DAWG(Directed Acylic Word Graph)는 대규모 단어 목록과 사전을 저장하고 검색하기 위한 데이터 구조입니다. 특정 유형의 데이터에 대해서는 .NET Dictionary 클래스보다 40배 더 효율적일 수 있습니다.

예를 들어, 내 웹 사이트는 디스크에서 56MB를 차지하고 로드하는 데 7초가 걸렸던 200만 단어 사전을 호스팅합니다(사전 및 BinarySerializer를 사용할 때). DAWG로 전환한 후 이제 디스크에서는 1.4MB, 로드하는 데 0.3초가 걸립니다.

이것이 어떻게 가능합니까? 표준 사전이 DAWG만큼 영리하지 않은 이유는 무엇입니까? 문제는 DAWG가 자연어 문자열에서는 잘 작동하지만 라이센스 키(OIN1r4Be2su+UXSeOj0TaQ)와 같이 생성된 문자열에서는 잘 작동하지 않을 수 있다는 것입니다. 인간의 언어 단어는 능력 , 가능성 , 민첩성 등의 공통 문자 시퀀스 를 많이 갖는 경향이 있으며 알고리즘은 이러한 시퀀스를 찾아 여러 단어에 대해 한 번만 저장함으로써 이를 활용합니다. DAWG는 DNA 데이터(유전자 서열)를 나타내는 데에도 유용한 것으로 입증되었습니다. DAWG의 역사는 1985년까지 거슬러 올라갑니다. 더 많은 배경을 알고 싶다면 Google DAWG 또는 DAFSA(결정적 비순환 유한 상태 자동 장치)를 참조하세요.

DawgSharp는 많은 것 중 하나인 DAWG의 구현입니다. 무엇이 특별할까요?

순수 C#으로 작성되었으며 MSIL(AnyCPU)로 컴파일되고 .NET 3.5 이상에서 실행됩니다.
종속성이 없습니다.
키의 문자에는 제한이 없습니다. 일부 경쟁 구현에서는 영문자 26자만 허용합니다. 이 구현은 모든 유니코드 문자를 처리합니다.
압축 알고리즘은 모든 노드를 한 번만 방문하므로 매우 빠릅니다(200만 단어 목록의 경우 5초).
즉시 사용 가능한 지속성을 제공합니다. Load/Save 호출하여 데이터를 디스크에 쓰고 다시 읽습니다.
단위 테스트(Visual Studio 테스트 프레임워크 사용)가 있습니다.
몇 시간에 걸친 성능 프로파일링 세션을 거쳤기 때문에 속도는 거의 빠릅니다. 이를 더 빠르게 만드는 다음 단계는 IL에서 관련 코드를 다시 작성하는 것입니다.
GC 친화적입니다. 가비지 컬렉터는 사전이 수백만 개의 문자열을 저장하는 3개의 큰 정수 배열만 볼 수 있습니다.

용법

이 예에서는 사전을 생성하여 디스크에 쓰는 프로그램과 해당 파일을 로드하고 조회에 읽기 전용 사전을 사용하는 프로그램 등 두 프로그램이 포함된 사용 시나리오를 시뮬레이션합니다.

먼저 이 리포지토리를 복제하거나 NuGet 패키지를 설치하여 코드를 가져옵니다.

DawgBuilder 개체를 만들고 채웁니다.

 var words = new [ ] { " Aaron " , " abacus " , " abashed " } ;

var dawgBuilder = new DawgBuilder < bool > ( ) ; // <bool> is the value type.
                                             // Key type is always string.
foreach ( string key in words )
{
    dawgBuilder . Insert ( key , true ) ;
}

(또는 var dawgBuilder = words.ToDawgBuilder(key => key, _ => true); )

압축된 버전을 얻고 디스크에 저장하려면 BuildDawg 호출하세요.

 Dawg < bool > dawg = dawgBuilder . BuildDawg ( ) ; 
// Computer is working.  Please wait ...

using ( var file = File . Create ( " DAWG.bin " ) ) 
    dawg . SaveTo ( file ) ;

이제 파일을 다시 읽고 특정 단어가 사전에 있는지 확인하십시오.

 var dawg = Dawg < bool > . Load ( File . Open ( " DAWG.bin " ) ) ;

if ( dawg [ " chihuahua " ] )
{
    Console . WriteLine ( " Word is found. " ) ;
}

값 유형, <TPayload>

Dawg 및 DawgBuilder 클래스는 <TPayload> 라는 템플릿 매개변수를 사용합니다. 원하는 유형이 될 수 있습니다. 단어가 사전에 있는지 테스트하려면 bool이면 충분합니다. int 나 string 또는 사용자 정의 클래스로 만들 수도 있습니다. 그러나 한 가지 중요한 제한 사항을 조심하십시오. DAWG는 TPayload가 취할 수 있는 값 세트가 상대적으로 작은 경우에만 잘 작동합니다. 작을수록 좋습니다. 예를 들어, 각 단어에 대한 정의를 추가하면 각 항목이 고유해지며 그래프가 트리가 됩니다(나쁘지 않을 수도 있습니다!).

MatchPrefix()

DAWG의 또 다른 매력적인 측면 중 하나는 특정 하위 문자열로 시작하는 모든 단어를 효율적으로 검색하는 기능입니다.

dawg . MatchPrefix ( " awe " )

위 쿼리는 awe, aweful 및 awesome 과 같은 키를 포함할 수 있는 IEnumerable<KeyValuePair> 를 반환합니다. dawg.MatchPrefix("") 호출은 사전의 모든 항목을 반환합니다.

대신 접미사로 조회해야 하는 경우 MatchSuffix 메서드가 없습니다. 그러나 반전된 키를 추가한 다음 반전된 키에 대해 MatchPrefix()를 사용하면 원하는 효과를 얻을 수 있습니다.

dawgBuilder . Insert ( " ability " . Reverse ( ) , true ) ;
.. .
dawg . MatchPrefix ( " ility " . Reverse ( ) )

GetPrefixes()

GetPrefixes()는 키가 주어진 문자열의 하위 문자열인 모든 사전 항목을 반환합니다. 예를 들어:

dawg . GetPrefixes ( " awesomenesses " )

awe, awesome, awesomeness 및 finally awesomenesses 와 같은 키를 반환할 수 있습니다.

GetLongestCommonPrefixLength()

또 다른 멋진 기능은 int GetLongestCommonPrefixLength(IEnumerable<char> word) 메서드입니다. word 사전에서 발견되면 해당 단어의 길이를 반환합니다. 그렇지 않은 경우 사전에서 찾은 가장 긴 단어의 길이를 반환하며 이는 주어진 단어의 시작이기도 합니다. 예를 들어 prepare는 사전에 있지만 preempt는 그렇지 않은 경우 dawg.GetLongestCommonPrefixLength("preempt") "pre"의 길이인 3을 반환합니다.

스레드 안전성

DawgBuilder 클래스는 스레드로부터 안전 하지 않으며 특정 시간에 하나의 스레드에서만 액세스해야 합니다.

Dawg 클래스는 변경할 수 없으므로 스레드로부터 안전합니다.

멀티도그

MultiDawg 클래스는 매우 메모리 효율적인 방식으로 단일 문자열 키에 대해 여러 값을 저장할 수 있습니다.

향후 계획

더 많은 사용 시나리오

API는 특정 사용 시나리오(위 참조)에 맞게 설계되었으며, 압축된 후 사전에 새 단어를 추가하는 등 다른 시나리오를 지원하도록 확장될 수 있습니다. 나는 이것이 필요하지 않았기 때문에 구현되지 않았습니다. 어떤 예외도 발생하지 않습니다. Dawg 클래스에는 Insert 메서드가 없습니다.