Menyimpan data n-gram

Saya berharap bisa bertukar pikiran sedikit tentang masalah menyimpan data n- gram. Dalam proyek saya, saya mencoba untuk memecahkan masalah linguistik di mana saya tahu semua ( n -1) item data dan ingin secara statistik menebak n saya menggunakan interpolasi linier atas semua n- gram yang berlaku . (Ya, ada tagger yang memberikan tag ke kata-kata yang dikenal sesuai dengan leksikonnya dan pohon akhiran yang mencoba menebak jenis kata untuk kata-kata yang tidak diketahui; komponen n- gram yang dibahas di sini akan bertugas menyelesaikan ambiguitas.)

Pendekatan awal saya adalah menyimpan semua n- gram yang diamati (untuk n = 1..3, yaitu monogram, bigram, trigram) data dalam masing-masing basis data SQL dan menyebutnya sehari. Tetapi persyaratan proyek saya dapat berubah untuk memasukkan panjang vektor lainnya ( n ), dan saya ingin aplikasi saya beradaptasi dengan 4-gram tanpa banyak pekerjaan (memperbarui skema, memperbarui kode aplikasi, dll.); idealnya, saya hanya akan memberitahu aplikasi saya untuk bekerja dengan 4-gram sekarang tanpa harus banyak mengubah kode (atau sama sekali) dan melatih datanya dari sumber data yang diberikan.

Singkatnya, semua persyaratan:

• Kemampuan untuk menyimpan data n- gram (awalnya untuk n = {1, 2, 3}
• Kemampuan untuk mengubah jenis n- gram apa yang harus digunakan (di antara aplikasi yang berjalan)
• Kemampuan untuk (kembali) melatih data n- gram (di antara aplikasi yang berjalan)

• Kemampuan untuk menanyai penyimpanan data (misalnya jika saya telah mengamati A, B, C, saya ingin mengetahui item yang paling sering diamati untuk apa yang mungkin terjadi setelah menggunakan set data 4, 3, 2, 1 1 gram saya yang terlatih )

  Aplikasi ini kemungkinan besar akan sangat berat, set data kemungkinan besar tidak akan dilatih ulang sesering itu

• Solusi ini menggunakan .NET Framework (hingga 4.0)

Sekarang desain apa yang lebih cocok untuk tugas seperti itu?

• Tabel tetap yang dikelola oleh server SQL (MSSQL, MySQL, ...) untuk setiap n (mis. Tabel khusus untuk bi-gram, tri-gram, dll.)
• Atau solusi basis data dokumen NoSQL yang menyimpan n -1 pertama sebagai kunci dokumen, dan dokumen itu sendiri berisi nilai ke- n dan frekuensi yang diamati?
• Atau sesuatu yang berbeda?

Karena Anda tidak akan tahu kisaran optimal N, Anda pasti ingin dapat mengubahnya. Misalnya, jika aplikasi Anda memprediksi kemungkinan teks tertentu adalah bahasa Inggris, Anda mungkin ingin menggunakan karakter N-gram untuk N 3..5. (Itulah yang kami temukan secara eksperimental.)

Anda belum membagikan detail tentang aplikasi Anda, tetapi masalahnya cukup jelas. Anda ingin mewakili data N-gram dalam database relasional (atau solusi berbasis dokumen NoSQL). Sebelum menyarankan solusi saya sendiri, Anda mungkin ingin melihat pendekatan berikut:

1. Bagaimana cara terbaik menyimpan Google ngrams dalam basis data?
2. Menyimpan n-gram dalam basis data dalam <n jumlah tabel
3. Mengelola Google Web 1T 5-gram dengan Database Relasional

Sekarang, setelah tidak membaca salah satu tautan di atas, saya menyarankan pendekatan database relasional sederhana menggunakan beberapa tabel, satu untuk setiap ukuran N-gram. Anda bisa meletakkan semua data dalam satu tabel dengan kolom maksimum yang diperlukan (mis. Menyimpan bigrams dan trigram di ngram_4, membiarkan kolom terakhir kosong), tapi saya sarankan mempartisi data. Bergantung pada mesin basis data Anda, satu tabel dengan banyak baris dapat berdampak negatif terhadap kinerja.

  create table ngram_1 (
      word1 nvarchar(50),
      frequency FLOAT,
   primary key (word1));

  create table ngram_2 (
      word1 nvarchar(50),
      word2 nvarchar(50),
      frequency FLOAT,
   primary key (word1, word2));

  create table ngram_3 (
      word1 nvarchar(50),
      word2 nvarchar(50),
      word3 nvarchar(50),
      frequency FLOAT,
   primary key (word1, word2, word3));

  create table ngram_4 (
      word1 nvarchar(50),
      word2 nvarchar(50),
      word3 nvarchar(50),
      word4 nvarchar(50),
      frequency FLOAT,
   primary key (word1, word2, word3, word4));

Selanjutnya, saya akan memberi Anda pertanyaan yang akan mengembalikan kata berikutnya yang paling mungkin diberikan pada semua tabel ngram Anda. Tetapi pertama-tama, berikut adalah beberapa contoh data yang harus Anda masukkan ke dalam tabel di atas:

  INSERT [ngram_2] ([word1], [word2], [frequency]) VALUES (N'building', N'with', 0.5)
  INSERT [ngram_2] ([word1], [word2], [frequency]) VALUES (N'hit', N'the', 0.1)
  INSERT [ngram_2] ([word1], [word2], [frequency]) VALUES (N'man', N'hit', 0.2)
  INSERT [ngram_2] ([word1], [word2], [frequency]) VALUES (N'the', N'bat', 0.7)
  INSERT [ngram_2] ([word1], [word2], [frequency]) VALUES (N'the', N'building', 0.3)
  INSERT [ngram_2] ([word1], [word2], [frequency]) VALUES (N'the', N'man', 0.4)
  INSERT [ngram_2] ([word1], [word2], [frequency]) VALUES (N'with', N'the', 0.6)
  INSERT [ngram_3] ([word1], [word2], [word3], [frequency]) VALUES (N'building', N'with', N'the', 0.5)
  INSERT [ngram_3] ([word1], [word2], [word3], [frequency]) VALUES (N'hit', N'the', N'building', 0.3)
  INSERT [ngram_3] ([word1], [word2], [word3], [frequency]) VALUES (N'man', N'hit', N'the', 0.2)
  INSERT [ngram_3] ([word1], [word2], [word3], [frequency]) VALUES (N'the', N'building', N'with', 0.4)
  INSERT [ngram_3] ([word1], [word2], [word3], [frequency]) VALUES (N'the', N'man', N'hit', 0.1)
  INSERT [ngram_3] ([word1], [word2], [word3], [frequency]) VALUES (N'with', N'the', N'bat', 0.6)
  INSERT [ngram_4] ([word1], [word2], [word3], [word4], [frequency]) VALUES (N'building', N'with', N'the', N'bat', 0.5)
  INSERT [ngram_4] ([word1], [word2], [word3], [word4], [frequency]) VALUES (N'hit', N'the', N'building', N'with', 0.3)
  INSERT [ngram_4] ([word1], [word2], [word3], [word4], [frequency]) VALUES (N'man', N'hit', N'the', N'building', 0.2)
  INSERT [ngram_4] ([word1], [word2], [word3], [word4], [frequency]) VALUES (N'the', N'building', N'with', N'the', 0.4)
  INSERT [ngram_4] ([word1], [word2], [word3], [word4], [frequency]) VALUES (N'the', N'man', N'hit', N'the', 0.1)

Untuk menanyakan kata berikutnya yang paling memungkinkan, Anda akan menggunakan kueri seperti ini.

  DECLARE @word1 NVARCHAR(50) = 'the'
  DECLARE @word2 NVARCHAR(50) = 'man'
  DECLARE @word3 NVARCHAR(50) = 'hit'
  DECLARE @bigramWeight FLOAT = 0.2;
  DECLARE @trigramWeight FLOAT = 0.3
  DECLARE @fourgramWeight FLOAT = 0.5

  SELECT next_word, SUM(frequency) AS frequency
  FROM (
    SELECT word2 AS next_word, frequency * @bigramWeight AS frequency
    FROM ngram_2
    WHERE word1 = @word3
    UNION
    SELECT word3 AS next_word, frequency * @trigramWeight AS frequency
    FROM ngram_3
    WHERE word1 = @word2
      AND word2 = @word3
    UNION
    SELECT word4 AS next_word, frequency * @fourgramWeight AS frequency
    FROM ngram_4
    WHERE word1 = @word1
      AND word2 = @word2
      AND word3 = @word3
    ) next_words
  GROUP BY next_word
  ORDER BY SUM(frequency) DESC

Jika Anda menambahkan lebih banyak tabel ngram, Anda perlu menambahkan klausa UNION lain untuk kueri di atas. Anda mungkin memperhatikan bahwa dalam permintaan pertama saya menggunakan word1 = @ word3. Dan dalam kueri kedua, word1 = @ word2 AND word2 = @ word3. Itu karena kita perlu menyelaraskan tiga kata dalam kueri untuk data ngram. Jika kita ingin kata berikutnya yang paling mungkin untuk urutan tiga kata, kita perlu memeriksa kata pertama dalam data bigram terhadap kata terakhir dari kata-kata dalam urutan.

Anda dapat mengubah parameter berat sesuai keinginan. Dalam contoh ini, saya mengasumsikan bahwa "n" gram ordinal yang lebih tinggi akan lebih dapat diandalkan.

PS Saya akan menyusun kode program untuk menangani sejumlah tabel ngram_N melalui konfigurasi. Anda dapat mengubah secara deklaratif program untuk menggunakan rentang N-gram N (1..6) setelah membuat tabel ngram_5 dan ngram_6.

Berlawanan dengan apa yang disarankan orang lain, saya sarankan untuk menghindari struktur data yang lebih kompleks daripada hashmap atau penyimpanan nilai kunci.

Ingat persyaratan akses data Anda: a) permintaan 99% - permintaan ngram "aaa-bbb-ccc" dan retreive nilai (atau 0) b) permintaan 1% - memasukkan / memperbarui hitungan ngram c tertentu) tidak ada (c).

Cara paling efektif adalah mengambilnya dengan satu pencarian. Anda dapat menggunakan pemisah di luar batas (atau melarikan diri) untuk menggabungkan n-gram penuh dalam satu string (misalnya "alpha | beta | gamma" untuk 3gram, "alpha" untuk unigram, dll) dan hanya mengambilnya ( oleh hash itu). Begitulah cukup banyak perangkat lunak NLP melakukannya.

Jika data ngram Anda kecil (katakanlah, <1 gb) dan sesuai dengan memori, maka saya sarankan untuk menggunakan struktur memori dalam-program yang efisien (hashmaps, tree, mencoba, dll) untuk menghindari overhead; dan hanya membuat serial / deserialize ke file flat. Jika data ngram Anda adalah terabyte atau lebih, maka Anda dapat memilih toko nilai kunci NoSQL dipecah pada beberapa node.

Untuk kinerja ekstra, Anda mungkin ingin mengganti semua kata di mana-mana dengan id integer sehingga algoritma inti Anda tidak melihat string (lambat) sama sekali; maka sedikit berbeda untuk mengimplementasikan ide yang sama.

Bukan yang paling efisien, tetapi sederhana dan terhubung ke database seperti yang Anda inginkan:

Table: word
Colums:
word (int, primary key) - a unique identifier for each word
text (varchar) - the actual word

Table: wordpos
Columns:
document (int) - a unique identified for the document of this word
word (int, foreign key to word.word) - the word in this position
pos (int) - the position of this word (e.g., first word is 1, next is 2, ...)

wordpos harus memiliki indeks pada dokumen dan pos.

bigrams adalah:

select word1.text as word1, word2.text as word2
from wordpos as pos1, wordpos as pos2, word as word1, word as word2
where pos1.document = pos2.document
      and pos1.pos = pos2.pos - 1
      and word1.word = pos1.word
      and word2.word = pos2.word

Kemudian Anda dapat menghitung () dan mengelompokkan cara Anda ke frekuensi dan barang.

Untuk mengubah ke trigram, mudah untuk membuat string ini untuk memasukkan kata3.

Saya sudah melakukan ini sebelumnya sebenarnya (meskipun SQL di sana mungkin sedikit berkarat). Saya menetap di satu set file datar yang bisa dicari dengan mudah kemudian streaming dari disk. Agak tergantung pada perangkat keras Anda bagaimana melakukannya dengan lebih baik.

Saat mencoba meningkatkan penelusuran sederhana aplikasi saya ke bigrams dan trigram dari unigrams, pada dasarnya, saya melihat pertanyaan Anda.

Jika salah satu persyaratan adalah kemampuan untuk menanyakan sistem file atau basis data yang terdistribusi, maka ini mungkin menarik bagi Anda juga: makalah Pibiri dan Venturini 2018 "Menangani Data N-Gram Secara Besar-besaran Secara Efisien" menguraikan cara efisien untuk menyimpan data n-gram di ketentuan runtime dan ruang. Mereka telah menawarkan implementasi mereka di https://github.com/jermp/tongrams

Setiap "n" dari n-gram disimpan dalam tabel terpisah yang diakses oleh fungsi hash minimum sempurna dengan kemampuan pilih dan kueri yang sangat cepat. Tabel statis dan dibangun oleh kode utama menggunakan input dalam format file teks Google n-gram.

Saya belum menggunakan kode, tetapi ada banyak cara yang Anda bisa dengan persyaratan terbuka Anda dari mana pertanyaan Anda berasal.

Satu cara: jika .NET yang setara dengan servlet digunakan dengan database atau datastore, dan jika Anda perlu menghemat ruang penyimpanan, maka menyimpan setiap tabel ngram dalam bentuk biner di database / datastore sebagai tabel adalah satu opsi (satu basis data) / tabel datastore untuk file statis yang dihasilkan dari kode ngram efisien untuk semua 1-gram, yang lain untuk semua 2-gram, dll). Kueri akan dijalankan dengan menjalankan kode n-gram yang efisien (dibungkus agar dapat diakses oleh servlet Anda). Ini merupakan upaya untuk membuat database terdistribusi yang menggunakan kode n-gram efisien untuk mengakses file pada sistem file terdistribusi. Perhatikan bahwa tabel database binary / datastore masing-masing memiliki batasan ukuran file dari sistem file yang mendasarinya.