Wydajny model bazy danych do przechowywania danych indeksowanych według n-gramów

12

Pracuję nad aplikacją, która wymaga utworzenia bardzo dużej bazy danych n-gramów, która istnieje w dużym korpusie tekstowym.

Potrzebuję trzech wydajnych typów operacji: wyszukiwanie i wstawianie indeksowane przez sam n-gram oraz sprawdzanie wszystkich n-gramów zawierających sub-n-gram.

Wydaje mi się, że baza danych powinna być gigantycznym drzewem dokumentów, a bazy danych dokumentów, np. Mongo, powinny być w stanie dobrze wykonać zadanie, ale nigdy nie korzystałem z nich na dużą skalę.

Znając format pytania stosu wymiany, chciałbym wyjaśnić, że nie pytam o sugestie dotyczące konkretnych technologii, ale raczej rodzaj bazy danych, której powinienem szukać, aby zaimplementować coś takiego na dużą skalę.

nlp databases Phonon
źródło
2
Myślę, że struktura, którą chcesz wdrożyć, jest „próbą” - czy nie możesz znaleźć bazy danych, która efektywnie działa z tą strukturą, czy też potrzebujesz własnej wersji w wybranym systemie RDBMS, nie mogę powiedzieć.
Neil Slater,

Odpowiedzi:

9

Zobacz Lucene NGramTokenizer

Czy na pewno nie możesz po prostu użyć Lucenu lub podobnych technik indeksowania?

Odwrócone indeksy zapiszą n-gram tylko raz, a następnie tylko identyfikatory dokumentów zawierające ngram; nie przechowują tego jako wysoce zbędny surowy tekst.

Jeśli chodzi o znalezienie ngramów, które zawierają podgram zapytania, zbudowałbym indeks na obserwowanych ngramach, np. Używając drugiego indeksu lucenu lub dowolnego innego indeksu podciągania, takiego jak drzewo trie lub sufiks. Jeśli Twoje dane są dynamiczne, prawdopodobnie Lucen jest rozsądnym wyborem, używając zapytań frazowych, aby znaleźć swoje n-gramy.

Ma ZAKOŃCZENIE - Anony-Mus
źródło
3

Zasadniczo do tego zadania możesz efektywnie wykorzystać dowolną bazę danych SQL z dobrym wsparciem indeksów opartych na drzewie B + (MySQL będzie pasował do Twoich potrzeb po prostu idealnie).

Utwórz 3 tabele:

  1. Tabela dokumentów, kolumny: identyfikator / dokument
  2. Tabela N-gramów: n_gram_id / n_gram
  3. Mapowanie między n-gramami a dokumentami: id_dokumentu / n_gram_dokumentu

Twórz indeksy na tabeli N-gram / łańcuch n_gram i tabeli mapowania / n_gram_id, również klucze podstawowe będą domyślnie indeksowane.

Twoje operacje będą wydajne:

  1. Wstawianie dokumentu: po prostu wyodrębnij wszystkie n-gramy i wstaw do tabeli dokumentów i N-gramów
  2. Wyszukiwanie in_gram będzie szybkie dzięki wsparciu indeksu
  3. Zapytanie o wszystkie n-gramy, które zawierają sub-n-gram: w 2 krokach - wystarczy zapytanie na podstawie indeksu wszystkich n-gramów, które zawierają sub-n-gram z 2. tabeli. Następnie - pobierz wszystkie odpowiednie dokumenty dla każdego z tych n-gramów.

Nie musisz nawet używać złączeń, aby wykonać wszystkie te operacje, więc indeksy bardzo pomogą. Również jeśli dane nie zmieszczą się w jednej maszynie - możesz zaimplementować schemat dzielenia, na przykład przechowywanie n_gramów uruchomionych z jednego serwera i oz na innym lub innym odpowiednim schemacie.

Możesz także użyć MongoDB, ale nie jestem pewien, jak dokładnie musisz wdrożyć schemat indeksowania. W przypadku MongoDB otrzymasz schemat dzielenia za darmo, ponieważ jest już wbudowany.

Maxim Galushka
źródło
1

Nie robiłem tego wcześniej, ale brzmi to jak zadanie dla bazy danych wykresów, biorąc pod uwagę pożądaną funkcjonalność. Oto demo w neo4j .

Emre
źródło