DawgSharp
1.0.0
[Пакет NuGet] [Получить коммерческую лицензию]
DAWG (направленный ациклический граф слов) — это структура данных для хранения и поиска больших списков слов и словарей. Для определенных типов данных он может быть в 40 раз эффективнее, чем класс .NET Dictionary .
Например, на моем веб-сайте размещен словарь на 2 миллиона слов, который раньше занимал 56 МБ на диске и загружался 7 секунд (при использовании Dictionary и BinarySerializer). После перехода на DAWG теперь занимает 1,4 мегабайта на диске и 0,3 секунды загружается.
Как это возможно? Почему стандартный словарь не такой умный, как DAWG? Дело в том, что DAWG хорошо работает со строками на естественном языке и может не работать с сгенерированными строками, такими как лицензионные ключи (OIN1r4Be2su+UXSeOj0TaQ). Слова человеческого языка, как правило, имеют много общих последовательностей букв, например, -ility в способностях , возможностях , ловкости и т. д., и алгоритм использует это преимущество, находя эти последовательности и сохраняя их только один раз для нескольких слов. DAWG также оказался полезным для представления данных ДНК (последовательностей генов). История DAWG берет свое начало в 1985 году. Для получения дополнительной информации используйте Google DAWG или DAFSA (детерминированный ациклический автомат с конечным состоянием).
DawgSharp — это реализация DAWG, одна из многих. Что делает его особенным?
Load/Save чтобы записать данные на диск и прочитать их обратно.В этом примере мы смоделируем сценарий использования, включающий две программы: одна для создания словаря и записи его на диск, а другая для загрузки этого файла и использования словаря, доступного только для чтения, для поиска.
Сначала получите код, клонировав этот репозиторий или установив пакет 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. " ) ;
} Классы Dawg и DawgBuilder принимают параметр шаблона <TPayload> . Это может быть любой тип, который вы хотите. Чтобы проверить, есть ли слово в словаре, достаточно логического значения. Вы также можете сделать его int , string или пользовательским классом. Но помните об одном важном ограничении. DAWG работает хорошо только тогда, когда набор значений, которые может принимать TPayload, относительно невелик. Чем меньше, тем лучше. Например, если вы добавите определение для каждого слова, это сделает каждую запись уникальной, и ваш график станет деревом (что может быть неплохо!).
Еще одна привлекательная сторона DAWG — это способность эффективно извлекать все слова, начинающиеся с определенной подстроки:
dawg . MatchPrefix ( " awe " ) Приведенный выше запрос вернет IEnumerable<KeyValuePair> , который может содержать такие ключи, как awe, aweful и Awesome . Вызов dawg.MatchPrefix("") вернет все элементы словаря.
Если вместо этого вам нужно выполнить поиск по суффиксу, метода MatchSuffix не существует. Но желаемого эффекта можно добиться, добавив перевернутые ключи, а затем применив MatchPrefix() к перевернутым клавишам:
dawgBuilder . Insert ( " ability " . Reverse ( ) , true ) ;
.. .
dawg . MatchPrefix ( " ility " . Reverse ( ) ) GetPrefixes() возвращает все элементы словаря, ключи которых являются подстроками данной строки. Например:
dawg . GetPrefixes ( " awesomenesses " )Могут возвращать такие ключи, как awe, Awesome, Awesomeness и, наконец, Awesomenesses .
Еще одна полезная функция — метод int GetLongestCommonPrefixLength(IEnumerable<char> word) . Если word найдено в словаре, оно вернет его длину; в противном случае он вернет длину самого длинного слова, найденного в словаре, которое также является началом данного слова. Например, если в словаре есть подготовка , а в словаре нет вытеснения , то dawg.GetLongestCommonPrefixLength("preempt") вернет 3, что соответствует длине "pre".
Класс DawgBuilder не является потокобезопасным, и в любой конкретный момент времени к нему должен обращаться только один поток.
Класс Dawg является неизменяемым и, следовательно, потокобезопасным.
Класс MultiDawg может хранить несколько значений в одном строковом ключе с очень эффективным использованием памяти.
API был разработан для конкретного сценария использования (см. выше) и может быть расширен для поддержки других сценариев, например, для добавления новых слов в словарь после его сжатия. Мне это просто не нужно, поэтому это не реализовано. Никаких исключений у вас не будет. В классе Dawg просто нет метода Insert .
Реализуйте интерфейс IDictionary как в DawgBuilder, так и в Dawg (#5).
DawgSharp распространяется по лицензии GPLv3, что означает, что его можно бесплатно использовать в проектах с открытым исходным кодом. Прочитать полную лицензию
Если вы хотите использовать DawgSharp в собственном проекте, приобретите коммерческую лицензию на http://morpher.co.uk.
