Cải tiến việc lưu trữ và truy vấn trong mô hình ngôn ngữ

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (5.66 MB, 24 trang )

Trang 1<div class="page_container" data-page="1">

Cao Trung Thụ

CẢI TIỀN VIỆC LƯU TRỮ VÀ TRUY VẤN

TRONG MƠ HÌNH NGƠN NGỮ

Chun ngành: Hệ thống thông tin

Mã số: 60.48.01.04

TOM TAT LUẬN VĂN THẠC SĨ

HÀ NỘI - 2014

</div>Trang 2<div class="page_container" data-page="2">

MỞ ĐẦU

Mơ hình ngơn ngữ là một trong những vấn đề quan trọng của lĩnh vực xử lý ngôn ngữ tự nhiên. Hiện nay có rất nhiều các ứng dụng thực tế sử dụng mơ hình ngơn ngữ như: kiểm tra lỗi chính tả, dịch máy hay nhận dạng tiếng nói... Đã có rất

nhiều các nghiên cứu về mơ hình ngơn ngữ được cơng bố rộng rãi trên thế giới với nhiều hướng tiếp cận khác nhau trong chủ yếu được xây dựng dựa trên mơ hình

Tuy nhiên, khi sử dụng mơ hình N-gram với một tập dữ liệu huấn luyện lớn sẽ phải lưu trữ và xử lý một dữ liệu lớn bao gồm các thông tin về các n-gram cũng

như xác xuất của chúng. Vấn đề này gây khó khăn cho việc lưu trữ và truy vấn bởi

sẽ cần một không gian bộ nhớ lớn dé lưu trữ những thông tin này cũng như tốc độ truy vấn bị giảm đi rất nhiều.

Với việc áp dụng những kỹ thuật như bảng băm, sắp xếp mảng, kỹ thuật nén

cùng với các kỹ thuật truy van tổ chức dưới dạng cây đã giúp giảm kích thước lưu

trữ cũng như tăng tốc độ truy vấn. Điều đó có ý nghĩa hết sức thực tế khi mà các ứng dụng của mơ hình ngơn ngữ ngày càng được sử dụng rộng rãi trong thực tế và

đang địi hỏi tính hiệu quả cao.

Luận văn “Cai tiễn việc lưu trữ và truy vấn trong mơ hình ngơn ngữ” sẽ

làm sáng tỏ những vấn đề về lưu trữ và truy vấn trong mơ hình ngơn ngữ N-gram cũng như đề xuất các giải pháp kỹ thuật để giải quyết bài tốn giảm kích thước bộ

nhớ lưu trữ cũng như tăng tốc độ truy vấn. Luận văn gồm 3 chương:

Chương 1: Mơ hình ngơn ngữ N-gram

Chương 2: Cải tiến kỹ thuật lưu trữ và truy van

Chương 3: Thử nghiệm và đánh giá

Trong đó phần nội dụng chính của luận văn sẽ tập trung ở chương 2 và chương 3 với những giải pháp kỹ thuật nhằm giảm bộ nhớ lưu trữ cho mơ hình ngơn ngữ N-gram cũng như tăng tốc độ truy vấn. Bên cạnh đó, luận văn cũng tiến hành

thử nghiệm và so sánh việc ap dụng những giải pháp kỹ thuật này với bộ công cụ

SRILM, bộ công cụ phô biến được sử dụng cho mô hình ngơn ngữ.

</div>Trang 3<div class="page_container" data-page="3">

CHƯƠNG 1: MƠ HÌNH NGƠN NGỮ N-GRAM

1.1.Ngơn ngữ tự nhiên và mơ hình ngơn ngữ

Ngôn ngữ tự nhiên là những ngôn ngữ được con người sử dụng trong giao

tiếp hàng ngày như nghe, nói, đọc, viết. Mặc dù con người có thé dé dàng hiểu nhưng dé máy tính hiểu được ngơn ngữ tự nhiên thì khơng dé dàng bởi ngơn ngữ tự nhiên có các quy luật về ngữ pháp và đơi khi cịn phụ thuộc vào ngữ cảnh.

Mơ hình ngơn ngữ được xây dựng nhằm mục đích giúp máy tính hiểu được ngôn ngữ tự nhiên thông qua việc thống kê các từ, các cụm từ trên một tập văn bản.

1.2. Mô hình ngơn ngữ N-gram

1.2.1. Những khái niệm cơ bản

Ngữ liệu (Corpus) là 1 dữ liệu tập hợp các văn bản, ngơn ngữ đã được số

hố hay cịn gọi là tập dữ liệu huấn luyện.

Các n-gram các cụm có độ dài n, bao gồm n kí tự hoặc n từ.

o Với n= I1, gọi là unigram, tập hợp các các chữ cái, các từ đơn.

o Với n=2, gọi là bigram, tap gồm hai chữ cái hoặc hai từ.

o Vớin=3, gọi là trigram, tập gồm các cụm ba chữ cái hoặc ba từ.

Tần số của một cum n-gram được ký hiệu là C (Count) là số lần xuất hiện của cum n-gram trong mơ hình ngơn ngữ. Phân biệt tan số C (count) với phan bic

(context offset) được sử dụng ở chương 2.

Xác xuất của một n-gram được ký hiệu là P hoặc p (Probablity) là xác suất của một cụm n-gram trong mơ hình ngơn ngữ.

1.2.2. Mơ hình ngơn ngữ N-gram

Với một mơ hình ngơn ngữ, việc căn bản nhất là cần thống kê các cụm n-gram va sau đó phải tính tốn và cho biết xác suất Cụm W¡W2Wa,_Wn-iWm là bao

nhiêu trong mơ hình ngơn ngữ đó. Theo cơng thức Bayes thì:

P(AB) = P(BỊA) * P(A) do đó: (1.1)

= P(w¡) * P(w›|w¡) * P(w:|wiw¿) *...* P(Wm|W1W2..Wm-1) (1.2)

</div>Trang 4<div class="page_container" data-page="4">

Sử dụng phương pháp xấp xi Markov bậc n sẽ có.

P(wm|WiWa...Wm-1) = P(Wm|Wm-nWm-nrt--- Wm-1) (1.3)

Nếu áp dụng xấp xi Markov, xác suất xuất hiện của một từ w„ được coi như chỉ phụ thuộc vào n từ đứng liền trước nó w„Wsa+i... Wm-1 mà khơng phải phụ thuộc vào tồn bộ dãy từ đứng trước w)w>...Wm-1. Như vậy, cơng thức tính xác suất

Cụm W¡W2Wa...Wn_¡Wm được tinh lại theo cơng thức dưới day:

P(WwiW2W:,..Wm-iWm) = P(w¡) * P(w¿|w¡) * P(ws|wiw¿) *...* P(Wm-I[Wm-n-Wm-n

...Wm-2) * P(Wm|Wm-nWm-n+l- --Wm-1) (1.4)

Từ đó có thể tính xác suất của bất kỳ một cụm từ nào dựa vào việc xây dựng một mơ hình ngơn ngữ trên cơ sở thống kê các cum từ có độ dài bé hơn n+1 từ. Với n là một số tự nhiên không cần quá lớn và cũng không phụ thuộc vào giá trị của m.

Mơ hình ngơn ngữ được xây dựng như trên đây được gọi là mơ hình ngơn

ngữ N-gram.

1.2.3. Khó khăn trong việc xây dựng mơ hình ngơn ngữ N-gram

1.2.3.1. Phân bố không déu của các n-gram

Khi sử dụng mơ hình N-gram theo cơng thức xác suất thì sự phân bố không

đều các cụm n-gram trong tập dữ liệu huấn luyện có thé dẫn đến các tính tốn

khơng chính xác. Khi các cụm n-gram phân bố không đều, nhiều cum n-gram không xuất hiện rất nhiều và nhiều cụm xuất hiện rất ít hoặc khơng xuất hiện dẫn đến việc

tính tốn xác suất khơng được chính xác. Vi dụ nếu một n-gram không xuất hiện thi sẽ làm cho xác suất cả câu chứa n-gram đó băng 0. Điều này dẫn đến những hạn chế

trong việc tính tốn và đánh giá trên mơ hình ngơn ngữ.

1.2.3.2. Cac n-gram dự thừa

Khi kích thước tập văn bản huấn luyện lớn, số lượng các cụm n-gram và kích thước của mơ hình ngơn ngữ cũng tăng theo. Điều đó khơng những gây khó khăn trong việc lưu trữ mà cịn làm cản trở tốc độ xử lý của mơ hình ngơn ngữ. Trong số các n-gram, có rất nhiều cụm n-gram dư thừa chi xuất hiện một vài lần nhưng hệ thống vẫn phải lưu trữ. Với việc sử dụng các phương pháp làm mịn cho phép tính tốn xác suất của các cum n-gram khơng có trong mơ hình ngơn ngữ, hồn tồn có

thê loại bỏ những n-gram có sơ lân xt hiện q nhỏ ra khỏi mơ hình ngơn ngữ.

</div>Trang 5<div class="page_container" data-page="5">

1.3. Các phương pháp làm mịn (Smoothing)

Các phương pháp làm mịn là các kỹ thuật được đưa ra dé khắc phục tinh

trạng các cum n-gram phân bố không đều. Về bản chat, các kỹ thuật làm mịn giúp

tính lại xác suất cho các cụm n-gram đảm bảo khơng có sự chênh lệch xác suất q

lớn giữa các cụm n-gram đặc biệt là cho phép tính xác suất của các cụm n-gram

không xuất hiện trong tập dữ liệu.

1.3.1. Các kỹ thuật triết khẩu (Discounting)

1.3.1.1. Kỹ thuật làm mịn Add-one

Với thuật toán Add-one, các unigram khi cộng thêm 1 vào tần số của mỗi cụm unigram, thì tổng số cụm unigram sé trở thành: M'=M+V (1.5)

Trong đó M là tổng số cụm unigram đã xuất hiện, V là kích thước bộ từ

vựng. Dé bảo toàn tổng tần số của tất cả các cụm n-gram không thay đổi thi tần số

mới của các cụm unigram được tính lại theo cơng thức: C;* = (C;+1) vg (1.6)

C; là tan số của cum unigram trước khi làm mịn bang thuật toán Add-one.

Như vậy, xác suât của các cụm unigram cũng được tinh lại như sau:

C* (C#])

* = ot

eM M+V (1-7)

Xét các cum n-gram với n>1, thay M bang C(W¡n¿i...W¡I) VÌ C(W¡n¿l...Wj-1)

chính là tông các cụm C(W¡a.,ị...W¡.¡ W). Vậy xác suat của cụm W¡n.¡...W¡.¡W¡ được

Công thức trên là phiên bản cải tiến của thuật tốn Add-one. Dé bao tồn tong xác suất của tất cả các cụm n-gram thi A được chọn trong khoảng [0, 1].

1.3.1.2. Kỹ thuật làm min Witten — BellT

Thuật toán WitteBell hoạt động dựa trên nguyên tắc khi gặp những cụm

n-gram có tân sơ 0 thi sẽ coi đây là lân dau tiên cụm từ nay xuât hiện. Với unin-gram,

</div>Trang 6<div class="page_container" data-page="6">

gọi T là số cụm unigram khác nhau đã xuất hiện còn M là tổng số các cụm unigram

đã thống kê. Do đó đó tổng số sự kiện sẽ là: (T+M).

Vậy xác suất để gặp cụm unigram lần đầu tiên được tính bằng: TT (1.10)

Gọi V là kích thước bộ từ vựng, cịn Z là sô cụm unigram chưa xuât hiện lan

nào: Z= V— T (1.11)

Xác suất xuất hiện của một cụm unigram chưa xuất hiện lần nao được tính

băng đây: P* = —— (1.12)

. Z(T+M) :

Va xác suat xuât hiện của các cum unigram có tân sơ khác 0 được tinh lại

cw)

Tim Vo c(w) là sô lân xuât hiện của cụm w. (1.13)

theo công thức: P(w) =

Cũng giống thuật toán Add-one, khi xét các cụm n-gram với n>1, thay M băng C(w¡n.i...W¡.i) thì xác suất của CUM W¡n¿i...WjIW¡ VỚI C(W¡n¿I...WjWj) = 0

được tính theo công thức sau:

gy

POw[ Wim WED = 20s WiI(C(Wyni.-WiD) £ TOW Wi)

Với C(Wi-ni1---Wi-1Wi) > 0, thi xác suat cum W¡n¿¡...W¡.¡W) tính băng cơng thức:

(Wi-nt1---Wi-1 Wi)

COWins1---WilW (1.15)

P(W;|Wy-ntt---Wi-l) =

(lWimaeeWn) > CG Wi) + (Wine We)

1.3.1.3. Kỹ thuật làm min Good-Turing

Thuật toán Good-Turing dựa trên việc tính tốn Ne, với Ne là số cụm n-gram xuat hién C lan. Nhu vay:

Np là số cụm n-gram có tần số 0 (số cụm n-gram khơng xuất hiện lần nào).

N¡ là sơ cụm n-gram có tân sơ 1 (sơ cum n-gram xt hiện 1 lân).

Ne có thể hiểu đơn giản là:N,= 3 (1.16)

</div>Trang 7<div class="page_container" data-page="7">

* g7

P(w) =< với N= = N.C (1.18)

Trén thuc té, sé khơng có tinh tốn va thay thế mọi tần số C bởi một tan số mới C*. Thay vào đó thường chọn một ngưỡng k nhất định, và chỉ thay thế tần số C

bởi tần số mới C* khi C nhỏ hơn hoặc băng k, còn nếu C lớn hơn k thì giữ nguyên tần số. Dé đơn giản chọn k đủ lớn dựa vào kết quả huấn luyện.

1.3.2. Thuật tốn truy hơi (Back-off)

Trong các phương pháp chiết khấu như Add-One hay Witten-Bell, nếu cụm

Wi.nri...W¡.¡W¡ không xuất hiện trong tập huấn luyện và cụm wW¡a;¡...W¡.¡ cũng khơng

xuất hiện, thì xác suất của cụm wW¡„:¡...W;.¡Ww; sau khi làm mịn vẫn băng 0. Phương

pháp truy hồi sẽ giải quyết vấn đề trên bằng cách ước lượng xác suất các cụm

n-gram chưa xuất hiện lần nao dựa vào xác suất của các cụm n-n-gram ngan hon có xác

suât khác 0. Cụ thê, xác suât của cụm w¡„.¡...W¡¡W¡ được tính lại theo công thức

— [P(wWilWin:i...Wi.L) nếu C(W¡n¿i...Wi.IWj) > 0

PB(Wi|Winrl...Wi-L) = ơ * Pa(wi|Wins2---Wi-1) nếu C(W¡a:i...WjWj) = 0 (1.19)

: . P(w¡j|w¡¡) nếu C(w;.;w;) > 0

Ap dung cho bigram, sẽ có: Pp(W¡|W¡.4) = (wiiwi,) nêu CwiiW) (1.20)

œ*P(wj) nếu C(w¡¡wj) = 0

Cơng thức trên có thể viết lại thành:

Ppg(Wij|w¡.i) = PQwilwia) + MWw¡¡w)) * a * P(w,) (1.21)

.. _ 1 nếu C(x) = 0

với UCD) = Í0 nếu C(x) > 0

Sự chính xác của mơ hình truy hồi phụ thuộc vào các tham số œ bởi vậy cần

những kỹ thuật dé giúp cho việc lựa chọn tham số a, thông thường œ sẽ phụ thuộc

vào một hàm. Dé thuật tốn chính xác hơn cần kết hợp nó với một thuật tốn chiết

khấu như Witten-Bell hay Good-Turing dé làm giảm xác suất của các cụm n-gram đã xuất hiện. Do đó, trong trường hợp tơng qt công thức như sau:

P(wWi|Wini .. .Wi-1) néu C(Wi-n+1 .. .W¡iWj) >0

Pa(WilWienst---Wi-t) = ơ * Pl (wil Wins2---Wi1) nếu C(W¡a¿i...WjpWj) = 0

(1.22)

</div>Trang 8<div class="page_container" data-page="8">

Trong đó P’ chính là xác suất của cụm n-gram khi áp dụng các thuật toán triết khấu.

1.3.3. Phương pháp nội suy (Interpolation)

Phương pháp nội suy có chung nguyên lý với phương pháp truy hồi tuy nhiên phương pháp mội suy khác phương pháp truy hồi ở điểm không phụ thuộc

vào sự xuất hiện của các cụm n-gram.

Cơng thức tính xác suất theo phương pháp nội suy như sau:

Pi(Wi|Wi-ntt---Wi) = AP(Wi|Wi-ne1---Wi-t) + (1-À)PI(W¡|[W¡-n+2-..W¡-1) (1.23) Ap dụng cho bigram và trigram sẽ có:

thé chọn tat cả 4 bằng nhau và bang 3 Tuy nhiên, cũng giống như phương pháp truy hồi, hồn tồn có thé chọn các tham số A như là một hàm của n-gram dé tăng

tính hiệu quả.

1.4. Các phương pháp cắt tỉa (Pruning)

Kỹ thuật cắt tỉa tập trung vào việc loại bỏ các cụm n-gram có tần số xuất hiện rất it trong mơ hình ngơn ngữ dé làm cho mơ hình ngơn ngữ được gon hơn, tiết kiệm bộ nhớ lưu trữ đồng thời cũng làm tăng độ chính xác trong việc tính tốn.

1.4.1. Phưng pháp loại bỏ (Cut-off)

Phương pháp loại bỏ hoạt động như sau: Nếu cụm n-gram xuất hiện ít hơn k

lần trong tập văn bản huấn luyện thì cum n-gram đó sẽ bi loại bỏ ra khỏi mơ hình ngơn ngữ. Khi tính tốn, nếu gặp lại các cụm n-gram này, thì tần số và xác suất của

chúng sẽ được tính tốn thơng qua các phương pháp làm mịn.

Trong một mơ hình ngơn ngữ, dé đảm bảo tính hiệu quả có thé sử dụng các tham số k khác nhau với các cụm n-gram có độ dài khác nhau. Vi dụ: với unigram

thì sử dụng k = 10, với bigram thì k = 1, và trigram thì k =5...

</div>Trang 9<div class="page_container" data-page="9">

iéc chọn tham số k cho phương pháp loại bỏ chính là van đề chính của kỹ

thuật này. Có hai phương pháp phơ biến dé lựa chọn tham số k. Mét /à, chạy thử

nhiều lần sau đó đánh giá độ hỗn loạn và lựa chọn k sao cho hiệu quả nhất. Hai 1a, chọn k dựa theo tỷ lệ phần trăm của số lượng các cụm n-gram, phải bảo đảm răng số cụm n-gram xuất hiện không quá k lần chiếm h% so với tổng số các cụm n-gram.

1.4.2. Phương pháp trọng số (Weighted difference)

Phương pháp loại bỏ chỉ quan tâm đến việc loại bỏ các cụm n-gram có tần số thấp trong khi phương pháp trọng số quan tâm đến nhiều thơng tin trong mơ hình ngôn ngữ hơn như mối quan hệ giữa các cụm gram, xác suất của từng cụm

n-gram... Như đã trình bày ở các phần trên, nếu một cụm n-gram không xuất hiện

trong tập huấn luyện thì xác suất của nó được ước lượng thông qua xác suất của các cụm n-gram ngắn hơn như trong phương pháp làm mịn truy hồi. Do đó, nếu xác

suất thực tế của một cum n-gram xấp xi với xác suất có được theo cơng thức truy

hơi thì sẽ khơng cần lưu trữ cum n-gram đó trong mơ hình ngơn ngữ nữa.

Độ chênh lệch = K * log((xác suất ban đầu) - log(xác suất truy hdi)) (1.26) K ở đây là tham số sử dụng trong phương pháp làm mịn Good Turing. Dựa

vào nhân tố chênh lệch ở trên sẽ quyết định giữ lại hay loại bỏ một cum n-gram.

Nếu độ chênh nhỏ hơn một ngưỡng nhất định, thì cụm n-gram đó sẽ bị loại bỏ khỏi

mơ hình ngơn ngữ.

1.5. Đánh giá mơ hình ngơn ngữ

Dé xây dựng được một hình ngơn ngữ hiệu qua cần phải có cách dé đánh giá chúng. Dưới đây là một số phương pháp phổ biến để đánh giá một mơ hình ngơn

ngữ N-gram:

o Độ đo thơng tin (Entropy)

o Độ hỗn loạn thông tin (Perplexity)o_ Tỉ lệ lỗi (Error rate)

o_ Đánh giá gián tiếp

1.6. Ứng dụng của mơ hình ngôn ngữ

o Dịch may

o Dich may thong ké

</div>Trang 10<div class="page_container" data-page="10">

CHƯƠNG 2: CẢI TIỀN KỸ THUẬT LƯU TRỮ VÀ TRUY VAN

2.1. Yêu cầu về bộ nhớ và tốc độ truy vấn trong mơ hình ngơn ngữ

Mơ hình ngơn ngữ N-gram là tài nguyên cơ bản trong dịch máy và dịch máy

thống kê. Bởi vậy khi máy tính cần xử lý một lượng thơng tin rất lớn trong mơ hình ngôn ngữ N-gram bao gồm thông tin về từ, tần số, xác suất, trọng số truy hồi... Do đó có thể thấy răng với một mơ hình ngơn ngữ N-gram thì việc giảm kích thước bộ nhớ lưu trữ cũng như tăng tốc độ truy vấn là rất quan trọng.

2.2. Biểu diễn mơ hình ngơn ngữ

2.2.1. Lượng tử hố các giá trị (Quantization values)

Trong mơ hình ngơn ngữ N-gram, để làm giảm kích thước của mơ hình ngơn

ngữ kỹ thuật lượng tử hoá các giá trị được sử dụng như hình 2.1 bên dưới.

</div>Trang 11<div class="page_container" data-page="11">

Thay vì lưu trữ giá trị thực của tần số hoặc xác suất thì sẽ lưu trữ các gia tri

đó dưới dang chi số. Sau đó, dé dam bảo các giá trị thực của tần số vẫn được lưu trữ

thì sử dụng một mạng phụ dé liên hệ các chỉ số với các giá trị thực tương ứng.

Như vậy, thay vì sử dụng sốt bit b với b = log, (tần số lớn nhất) dé lưu trữ tan số của một cụm n-gram, sẽ chỉ cần sử dụng một số bít b’ với b’ = log; (số phần tử

unique của tần số) cho mỗi cụm n-gram. Bởi b’ nhỏ hơn rất nhiều so với b, qua đó

sẽ tiết kiệm được bộ nhớ trong việc lưu trữ mơ hình ngơn ngữ.

2.2.2. Biêu diễn n-gram

Dé biểu diễn một n-gram trong sự liên kết giữa các n-gram với nhau ma cụ thé là sự liên kết giữa n-gram với (n-1)-gram, kỹ thuật biểu diễn ngầm tiền tố (encoding prefix) được sử dụng. Điểm mau chốt của kỹ thuật này là mỗi cum n-gram sẽ được biểu diễn bởi một cặp bao gồm từ cuối cùng của n-n-gram đó va phan

bù chỉ tới (n-1)-gram.

Nhu vậy với n-gram w" kết thúc bằng từ w, sẽ được biéu diễn đưới dạng một cặp giá trị như sau: w" = (wa, c(wTM')) trong đó c(w*”) được gọi là phan bù (context

offset) của w" chỉ tới (n-1)-gram w* còn w, là từ cuối cùng của cum n-gram w".

Hình 2.2 mơ tả chi tiết kỹ thuật lượng tử hoá các cặp giá trị (w,, c(wTM")).

4-grams 3-prams 2-prams 1-grams

</div>Trang 12<div class="page_container" data-page="12">

Như trên hình 2.2 biểu diễn hai cum n-gram “J love my country” và “I love

the islands”. Gia trị id 120, 121, 122, 123, 124, 125, 126, 127 tương ứng của các từ“T’, “love”, “the”, “islands”, “my”, “country”, “so”, “much”. Gia trị c = 10541 và

10523 của gram liên hệ của các từ cuối “country” và từ “islands” trong cum

4-gram với các cum tri4-gram tương ứng “J love my” và “I love the”. Gia tric =1121 và1019 của trigram liên hệ “my” va “the” trong trigram với cụm bigram “J love”. Vac

= 197 là biểu diễn quan hệ cua t “/ove” trong bigram với từ “7” trong unigram.

2.2.3. Cau trúc dữ liệu của mơ hình ngơn ngữ 2.2.3.1. Cau trúc dữ liệu cây Trie

Cấu trúc dữ liệu Trie biéu diễn mơ hình ngơn ngữ dưới dạng cây trong đó mỗi nút trên cây sẽ lưu trữ hai thông tin cơ bản sau: Mot là, thông tin về từ hay ký

tự của nút đó bao gồm từ hay ký tự cộng với tan số, trọng số truy hồi... Hai /à, thơng tin chỉ đến các nút con của nút đó (pointers). Hình 2.3 là mơ hình của một

Trie ứng với dữ liệu trong file ARPA.

</div>