Структура космического эффекта в памяти для отсортированного текста поддерживает префикс поиска -- c# поле с участием .net поле с участием algorithm поле с участием prefix поле с участием trie пол Связанный проблема

Space-efficient in-memory structure for sorted text supporting prefix searches


14
vote

проблема

русский

У меня есть проблема: мне нужен космический поиск файловой системы, основанных на префиксе файлового пути. Преобразование поиска отсортированного текста, другими словами. Используйте TRIE, вы говорите, и я думал то же самое. Проблема в том, что пытается неэффективным, а не без других трюков.

У меня есть честное количество данных:

    .
  • около 450 м в однократном тексте Unix-формата, списка на диске
  • около 8 миллионов строк
  • gzip по умолчанию компрессы до 31 м
  • bzip2 по умолчанию сжимает до 21 м

Я не хочу есть где угодно рядом с 450 м в памяти. На данный момент я был бы рад использовать где-то около 100 м, поскольку в форме префиксов много избыточности.

Я использую C # для этой работы, и простое реализация TRIE все равно потребует одного узла листьев для каждой строки в файле. Учитывая, что каждый узел листьев потребует некоторой ссылки на окончательный кусок текста (32 бита, скажем, индекс в массив строковых данных для минимизации дублирования строки), а накладные расходы на объект CLR представляют собой 8 байтов (проверено с использованием WINDBG / SOS) , я буду тратить и gt; 96 000 000 байтов в структурных накладных расходах без текстового хранения вообще.

Давайте посмотрим на некоторые из статистических атрибутов данных. При заполненном трибуне:

    .
  • Общие уникальные "куски" текста около 1,1 миллиона
  • Общие уникальные куски около 16 м на диске в текстовом файле
  • средняя длина кусочки составляет 5,5 символов, max 136
  • , когда не принимая во внимание дубликаты, около 52 миллионов символов в чанках
  • внутренние узлы TRIE в среднем около 6,5 детей с максимумом 44
  • около 1,8 м внутренних узлов.

Увеличение скорости создания листьев составляет около 15%, избыточное создание узла внутреннего узла составляет 22% - по избыточным созданию, я имею в виду листья и внутренние узлы, созданные во время конструкции TRIE, но не в финал TRIE как доля окончательного количества узлов каждого типа.

Вот анализ кучи от SOS, указывающий, где используется наибольшая память:

 <код>  [MT    ]--[Count]----[   Size]-[Class                                          ]  03563150       11         1584 System.Collections.Hashtable+bucket[]  03561630       24         4636 System.Char[]  03563470        8         6000 System.Byte[]  00193558      425        74788      Free  00984ac8    14457       462624 MiniList`1+<GetEnumerator>d__0[[StringTrie+Node]]  03562b9c        6     11573372 System.Int32[] *009835a0  1456066     23297056 StringTrie+InteriorNode  035576dc        1     46292000 Dictionary`2+Entry[[String],[Int32]][] *035341d0  1456085     69730164 System.Object[] *03560a00  1747257     80435032 System.String *00983a54  8052746     96632952 StringTrie+LeafNode   

Dictionary<string,int> используется для отображения кусков строк, чтобы индексы в <код> List<string> и могут быть отброшены после конструкции TRIE, хотя GC, кажется, не удаляет его (Пара явных коллекций было выполнено до этого дампа) - <Код> !gcroot в SOS не указывает никаких корней, но я ожидаю, что более поздний GC освободит его.

<Код> MiniList<T> - это замена List<T> с использованием точно размером (т.е. линейный рост, <код> O(n^2) photower Apply) <код> <input type="text" [ngClass]="{red: sampledetails.rules[0].query3.dirty}" class="form-control" name="query3" id="query3" [(ngModel)]="sampledetails.rules[0].query3" #query3="ngModel"> 0 код>, чтобы избежать пространства потери; Это тип значения и используется <код> <input type="text" [ngClass]="{red: sampledetails.rules[0].query3.dirty}" class="form-control" name="query3" id="query3" [(ngModel)]="sampledetails.rules[0].query3" #query3="ngModel"> 1 для отслеживания детей. Это <код> <input type="text" [ngClass]="{red: sampledetails.rules[0].query3.dirty}" class="form-control" name="query3" id="query3" [(ngModel)]="sampledetails.rules[0].query3" #query3="ngModel"> 2 добавляется в <код> <input type="text" [ngClass]="{red: sampledetails.rules[0].query3.dirty}" class="form-control" name="query3" id="query3" [(ngModel)]="sampledetails.rules[0].query3" #query3="ngModel"> 3 ворс.

Итак, если я оттудаю «интересные» предметы (отмеченные <код> <input type="text" [ngClass]="{red: sampledetails.rules[0].query3.dirty}" class="form-control" name="query3" id="query3" [(ngModel)]="sampledetails.rules[0].query3" #query3="ngModel"> 4 ), я получаю около 270 м, что лучше, чем сырой текст на диске, но все еще не достаточно близко к моей цели. Я подумал, что накладные расходы .NET объекта был слишком много, и создал новую «тонкую» TRIE, используя только массивы типа «Значение» для хранения данных:

 <код> <input type="text" [ngClass]="{red: sampledetails.rules[0].query3.dirty}" class="form-control" name="query3" id="query3" [(ngModel)]="sampledetails.rules[0].query3" #query3="ngModel"> 5  

Эта структура принесла сумму данных до 139 м, и все еще является эффективно переследуемым TRIE для операций только для чтения. И потому что это так просто, я могу положить триветично сохранить его на диск и восстановить его, чтобы избежать стоимости F воссоздание истина каждый раз.

Так, любые предложения для более эффективных структур для поиска префикса, чем TRIE? Альтернативные подходы, которые я должен рассмотреть?

Английский оригинал

I have a problem: I need space-efficient lookup of file-system data based of file path prefix. Prefix searching of sorted text, in other words. Use a trie, you say, and I thought the same thing. Trouble is, tries are not space-efficient enough, not without other tricks.

I have a fair amount of data:

  • about 450M in a plain-text Unix-format listing on disk
  • about 8 million lines
  • gzip default compresses to 31M
  • bzip2 default compresses to 21M

I don't want to be eating anywhere close to 450M in memory. At this point I'd be happy to be using somewhere around 100M, since there's lots of redundancy in the form of prefixes.

I'm using C# for this job, and a straightforward implementation of a trie will still require one leaf node for every line in the file. Given that every leaf node will require some kind of reference to the final chunk of text (32 bits, say an index into an array of string data to minimize string duplication), and CLR object overhead is 8 bytes (verified using windbg / SOS), I'll be spending >96,000,000 bytes in structural overhead with no text storage at all.

Let's look at some of the statistical attributes of the data. When stuffed in a trie:

  • total unique "chunks" of text about 1.1 million
  • total unique chunks about 16M on disk in a text file
  • average chunk length is 5.5 characters, max 136
  • when not taking into account duplicates, about 52 million characters total in chunks
  • Internal trie nodes average about 6.5 children with a max of 44
  • about 1.8M interior nodes.

Excess rates of leaf creation is about 15%, excess interior node creation is 22% - by excess creation, I mean leaves and interior nodes created during trie construction but not in the final trie as a proportion of the final number of nodes of each type.

Here's a heap analysis from SOS, indicating where the most memory is getting used:

 [MT    ]--[Count]----[   Size]-[Class                                          ]  03563150       11         1584 System.Collections.Hashtable+bucket[]  03561630       24         4636 System.Char[]  03563470        8         6000 System.Byte[]  00193558      425        74788      Free  00984ac8    14457       462624 MiniList`1+<GetEnumerator>d__0[[StringTrie+Node]]  03562b9c        6     11573372 System.Int32[] *009835a0  1456066     23297056 StringTrie+InteriorNode  035576dc        1     46292000 Dictionary`2+Entry[[String],[Int32]][] *035341d0  1456085     69730164 System.Object[] *03560a00  1747257     80435032 System.String *00983a54  8052746     96632952 StringTrie+LeafNode 

The Dictionary<string,int> is being used to map string chunks to indexes into a List<string>, and can be discarded after trie construction, though GC doesn't seem to be removing it (a couple of explicit collections were done before this dump) - !gcroot in SOS doesn't indicate any roots, but I anticipate that a later GC would free it.

MiniList<T> is a replacement for List<T> using a precisely-sized (i.e. linear growth, O(n^2) addition performance) T[] to avoid space wastage; it's a value type and is used by InteriorNode to track children. This T[] is added to the System.Object[] pile.

So, if I tot up the "interesting" items (marked with *), I get about 270M, which is better than raw text on disk, but still not close enough to my goal. I figured that .NET object overhead was too much, and created a new "slim" trie, using just value-type arrays to store data:

class SlimTrie {     byte[] _stringData; // UTF8-encoded, 7-bit-encoded-length prefixed string data      // indexed by _interiorChildIndex[n].._interiorChildIndex[n]+_interiorChildCount[n]     // Indexes interior_node_index if negative (bitwise complement),     // leaf_node_group if positive.     int[] _interiorChildren;      // The interior_node_index group - all arrays use same index.     byte[] _interiorChildCount;     int[] _interiorChildIndex; // indexes _interiorChildren     int[] _interiorChunk; // indexes _stringData      // The leaf_node_index group.     int[] _leafNodes; // indexes _stringData      // ... } 

This structure has brought down the amount of data to 139M, and is still an efficiently traversable trie for read-only operations. And because it's so simple, I can trivially save it to disk and restore it to avoid the cost of recreating the trie every time.

So, any suggestions for more efficient structures for prefix search than trie? Alternative approaches I should consider?

</div
              
     
     

Список ответов

2
 
vote
vote
Лучший ответ
 

Поскольку только 1,1 миллиона кусков вы можете индексировать кусок, используя 24 бита вместо 32 бит и экономию там.

Вы также можете сжать куски. Возможно Кодирование Хаффмана - хороший выбор. Я также попробую следующую стратегию: вместо того, чтобы использовать символ в качестве символа для кодирования, вы должны кодировать переходы символов. Таким образом, вместо того, чтобы смотреть на вероятность появления персонажа, посмотрите на вероятность перехода в Markov Chain / A> Где состояние является текущим символом.

 

Since there are only 1.1 million chunks, you can index a chunk using 24 bits instead of 32 bits and save space there.

You could also compress the chunks. Perhaps Huffman coding is a good choice. I would also try the following strategy: instead of using a character as a symbol to encode, you should encode character transitions. So instead of looking at the probability of a character appearing, look at the probability of the transition in a Markov chain where the state is the current character.

</div
 
 
       
       
1
 
vote

Вы можете найти научную статью, подключенную к вашей проблеме здесь (цитата авторов:« Эксперименты показывают, что наш индекс поддерживает быстрые запросы в пространстве занятость, которое близко к одному достижемую, сжав словарь строки через GZIP, BZIP или PPMDI. "- Но, к сожалению, бумага только оплата). Я не уверен, насколько трудно реализовать эти идеи. Авторы этой статьи имеют a Сайт Где вы можете найти также реализации (в разделе «Коллекция индекса») различных алгоритмов сжатого индекса .

Если вы хотите продолжать свой подход, обязательно проверим веб-сайты о Crit-Bit Деревья и Radix дерево .

 

You can find a scientific paper connected to your problem here (citation of the authors: "Experiments show that our index supports fast queries within a space occupancy that is close to the one achievable by compressing the string dictionary via gzip, bzip or ppmdi." - but unfortunately the paper is payment only). I'm not sure how difficult these ideas are to implement. The authors of this paper have a website where you can find also implementations (under "Index Collection") of various compressed index algorithms.

If you want to go on with your approach, make sure to check out the websites about Crit-bit trees and Radix tree.

</div
 
 
       
       
0
 
vote

Идея вне стены: вместо Trie a hash table. У вас будет в памяти просто хэш и строковые данные, возможно, сжатые.

или вы можете позволить себе одну страницу читать? Только хэш и местоположение файла в памяти, извлеките «страницу» с линиями, соответствующими, что HASH, предположительно небольшое количество упорядоченных линий, поэтому очень быстро искать в случае столкновений.

 

Off-the-wall idea: Instead of a trie a hash table. You'd have in memory just the hash and the string data, perhaps compressed.

Or can you afford one page read? Only hash and file position in memory, retrieve the "page" with lines matching that hash, presumably small number of ordered lines, hence very quick to search in the event of collisions.

</div
 
 
       
       

Связанный проблема

0  Ресурс кастинга COSMOS БД в интерфейс  ( Cosmos db casting resource to interface ) 
Если я хочу вернуть объект на основе интерфейса в Cosmodb, как бы я это сделал? Мой интерфейс: <код> namespace Test { public interface IPerson { ...

0  Что это за кодирование? (Найдено в Outlook / filitory)  ( What is this encoding found in outlook filesite ) 
Я работаю над Addin Outlook VSTO, который будет подключать аддин для файлового файла imagiate, я в настоящее время пытаюсь получить доступ к идентификатору в ...

1  Как получить доступ к конкретной группе в CollectionSourceSource.View.Groups  ( How to access a specific group within collectionviewsource view groups ) 
У меня есть .NET Имя Свойство. Я хотел бы знать, есть ли способ выбрать определенную подгруппу на достаточно высоком уровне без необходимости оценивать н...

1  C # Словарь <Объект, t> Значение поиска  ( C sharp dictionaryobject t lookup value ) 
Не уверены, как лучшее фразу, наверное, это, вероятно, почему у меня трудно посмотреть это. Вот приложение для пробной консоли для демонстрации моего значения...

0  Обновление данных с той же первичным ключом  ( Updating data with same primary key ) 
Я читаю данные из файла CSV и добавление данных в базу данных. Во время вставки данных в базу данных я хочу обновить данные с той же первичной клавишей. e.g...

3  OnleftClick & OnrightClick JavaScript Функции  ( Onleftclick onrightclick javascript functions ) 
В моем боковом коде сервера я динамически строим таблицу и именно сейчас я добавляю следующий код, чтобы обрабатывать Щелчок строки. <код> tr.Attributes.Add...

0  Каркас экспорта данных или инструменты  ( Data export framework or tools ) 
Есть ли какие-либо данные экспорта данных в .NET или что-то. Мне нужно устройство набора инструментов для экспорта наследие и данных из более старых / устарев...

0  Получить объект атрибута из inamedtypesymbol.getttributes () I.e. Объект Attribradate?  ( Get attribute object from inamedtypesymbol getattributes i e attributedata ob ) 
Я определил следующий атрибут <код> [AttributeUsage(AttributeTargets.Class)] class DemoAttribute : Attribute { public string SomeInfo { get; } public D...

-6  Linux и CSHARP, проверьте, если файл / папка не существует в Linux, если так, запустите mkdir через csharp ssh - [закрыто]  ( Linux and csharp check if file folder doesnt exist in linux if so run mkdir ) 
<в сторону CLASS = "S-NEWACTS S-WELTIVE__info JS-Post-New Imide MB16« Роль = «Статус»> закрыт . Этот вопрос нуждается в Детали или ясность . В настоящее...

-1  Какой поток Nibernate Pure? [закрыто]  ( What is the flow of nhibernate pure ) 
<в сторону CLASS = "S-NEWACTS S-WELTIVE__info JS-Post-New Imide MB16« Роль = «Статус»> закрыт . Этот вопрос должен быть больше Фокусированный . В настоя...

3  Как я могу использовать список?  ( How can i use listdictionary ) 
Я могу заполнить мой список listdicticatic, но, если запущена ошибка, возвращается мне в "Foreach (kne ky ky в ld.keys)" (исключение недействительной операции...

5  Объект к сопоставлению объекта  ( Object to object mapping utility ) 
Мне нравится чисто разделить публику и домен объекты (Итак, nhibernate не поможет здесь) друг от друга, которые заставляют меня писать много кода, чтобы ото...

14  Datagridviewcomboboxcolumn Добавление различных элементов к каждой строке  ( Datagridviewcomboboxcolumn adding different items to each row ) 
Я создаю таблицу, используя datagridview, где пользователь может выбрать элементы из раскрывающегося списка в каждой ячейке. Чтобы упростить проблему, давайте...

0  Причина определенных ограничений на преобразования дисперсии в C #  ( Reason for certain restrictions on variance conversions in c sharp ) 
У меня есть несколько вопросов о том, как неявные преобразования между методом делегатов в отношении ковариации и контравариации реализуются в C #. <код> de...

1  EntityFramework 5 CodeFirst Rice родитель одного типа не обновляет / сохранение  ( Entityframework 5 codefirst child parent of the same type not updating saving ) 
У меня есть <код> class называется раздел <код> public class Section { public Section() { construct(0); } public Section(int order) { construct(ord...

Связанный проблема

0  Ресурс кастинга COSMOS БД в интерфейс 
0  Что это за кодирование? (Найдено в Outlook / filitory) 
1  Как получить доступ к конкретной группе в CollectionSourceSource.View.Groups 
1  C # Словарь <Объект, t> Значение поиска 
0  Обновление данных с той же первичным ключом 
3  OnleftClick & OnrightClick JavaScript Функции 
0  Каркас экспорта данных или инструменты 
0  Получить объект атрибута из inamedtypesymbol.getttributes () I.e. Объект Attribradate? 
-6  Linux и CSHARP, проверьте, если файл / папка не существует в Linux, если так, запустите mkdir через csharp ssh - [закрыто] 
-1  Какой поток Nibernate Pure? [закрыто] 
3  Как я могу использовать список? 
5  Объект к сопоставлению объекта 
14  Datagridviewcomboboxcolumn Добавление различных элементов к каждой строке 
0  Причина определенных ограничений на преобразования дисперсии в C # 
1  EntityFramework 5 CodeFirst Rice родитель одного типа не обновляет / сохранение