Một phương pháp tìm kiếm thông tin dựa vào mã bch trong thư viện số

gọn hơn một số phương pháp đã có trước đây và 
dễ xử lý hơn. 
II - MÃ BCH (BOSE - CHAUDHARI - HOCQUENQHEM) 
Phát biểu hình thức bài toán như sau: 
Cho V là một tập hữu hạn và D là một tập con hữu hạn của V sao cho MaxdD|d| = t, trong đó |d| 
ký hiệu số phần tử thuộc d. Cho q là tập con phân biệt của V sao cho |q|  t. Tìm một ký hiệu và một 
giải thuật phù hợp để xử lý tự động cho phép một trong 
a> biểu diễn các phần tử thuộc D; 
b> quyết định, đối với mỗi một d  D, liệu d  q hay không. 
Chú ý: ở dạng này, bài toán mô tả một lớp rộng hơn các trạng thái xử lý dữ liệu thực so với chỉ 
bài toán tìm kiếm thông tin mô tả trước đó. 
Chúng tôi đề xuất biểu diễn các phần tử thuộc V bằng các r-bộ nhị phân và các phần tử thuộc D 
bằng mod 2 tổ hợp tuyến tính của r-bộ này. Vì tập tất cả r-bộ như thế là một không gian vector trên 
GF(2), như tổ hợp tuyến tính. Để đảm bảo có thể biểu diễn mỗi một tập d  D rõ ràng, chúng tôi yêu 
cầu không có hai tổ hợp tuyến tính như thế riêng biệt là bằng nhau. Hình thức hơn: một tập K phần tử 
của một không gian vector được coi là một mã chồng tuyến tính giải mã được có độ sâu t (DLS) nếu 
không có hai tổ hợp tuyến tính riêng biệt của b hoặc có phần tử ít hơn bằng nhau. 
Quan hệ giữa các yêu cầu áp đặt lên K bằng định nghĩa này và khái niệm phụ thuộc tuyến tính 
quen thuộc hơn là khái niệm trong lý thuyết mã, nghĩa là, K là một DSL nếu và chỉ nếu mọi tập con 
gồm có 2t hoặc ít hơn vector là độc lập tuyến tính. 
 2
Tiếp theo, chúng tôi trở lại câu hỏi về tìm kiếm DLS. Các thuộc tính của các tập như thế ở 
trường hợp tổng quát trong đó các vector là m-bộ phần tử từ một trường hữu hạn tuỳ ý được xem xét 
tại độ dài bởi Tallini và Segre, nhưng một ít kết quả của họ có thể được áp dụng vào trường hợp nhị 
phân GF(2). Tuy nhiên, các phương pháp tồn tại nhằm sinh ra các họ lớn của các tập như thế và xuất 
hiện do lí thuyết mã sửa lỗi tuyến tính. 
Một mã tuyến tính nhị phân là một không gian con trong không gian vector n-bộ trên GF(2) và 
vì vậy là một nhóm con của nhóm cộng tính n-bộ. Vì vậy, nó có thể mở rộng toàn bộ nhóm trong lớp 
modulo thành mã lớn hơn. Hơn nữa, vì sự lựa chọn một đầu lớp là tuỳ ý bên trong mỗi một lớp, thông 
thường lựa chọn một phần tử có trọng số cực tiểu như đầu lớp, vì điều này có thể được chỉ ra nhằm 
cực tiểu hoá xác suất giải mã đúng khi giải mã được dựa trên sự mở rộng lớp. Với quy ước này, đầu 
lớp phù hợp duy nhất với các lỗi có thể được hiệu chính bằng mã và một mã sửa t-lỗi chính xác ở 
trường hợp tất cả mẫu có trọng số t hoặc nhỏ hơn xuất hiện như các đầu lớp. 
Bây giờ, bất kỳ ma trận kiểm tra tính chẵn lẻ đối với một mã định rõ tính đồng cấu từ các lớp 
của mã trên không gian vector có (n - k)-bộ trên GF(2), với nhân bằng mã. Như vậy, nếu H là một ma 
trận kiểm tra tính chẵn lẻ và y là một (n - k)-bộ thì tập tất cả vector x sao cho xHT = y là một lớp. Quan 
trọng hơn, nếu x1 và x2 là các đầu lớp duy nhất do quy ước trọng số cực tiểu thì x1HT = x2HT  x1 = x2 
Như vậy, không có hai đầu lớp riêng biệt duy nhất x1 , x2 sao cho (x1 x2)HT = 0; nghĩa là, nhân của H 
(tức là mã) không chứa vector có trọng số nhỏ hơn 2t + 1 nếu mã sửa t lỗi. Điều này tạo ra kết quả là 
vì các vector trong không gian n chiều là các hàm đặc trưng đối với tổ hợp cột của H, không tập có 2t 
hoặc ít hơn cột của H là phụ thuộc tuyến tính. Vì vậy, các cột của bất kỳ ma trận kiểm tra tính chẵn lẻ 
đối với một mã sửa t lỗi là một mã chồng tuyến tính giải mã được có độ sâu t. 
Như vậy, dựa vào lực lượng của V và lực lượng cực đại của bất kỳ tập con thuộc D, chúng ta có 
thể tìm được một mã sửa lỗi sao cho các cột của một ma trận kiểm tra tính chẵn lẻ đối với mã đó là đủ 
để biểu diễn các phần tử của V và các tổ hợp tuyến tính của chúng biểu diễn các phần tử của D. Tính 
duy nhất của các đầu lớp do quy ước trọng số cực tiểu bảo đảm rằng nó có thể quyết định chỉ từ các 
đại diện của q và d, dù d  q hay không. Thực tế, có một phép thử mạnh có thể áp dụng vào mục đích 
này; phép thử sẽ được mô tả sau đây. 
Ví dụ: giả sử | V | = 16000 10dMax
D∈d
 
Điều này có thể tương ứng với tập tài liệu, mỗi một trong chúng được chỉ mục bằng cách lựa 
chọn không nhiều hơn 10 thuật ngữ chỉ mục từ một từ vựng có 16000 thuật ngữ. Chúng ta lựa chọn 
biểu diễn các phần tử của V bằng các cột của một ma trận kiểm tra tính chẵn lẻ đối với một mã BCH 
[14]. Tham chiếu các bảng về đa thức tối giản ở [14], chúng ta tìm thấy có một mã BCH có độ dài 
16383 và trọng số 21 yêu cầu 140 bit kiểm tra tính chẵn lẻ. Như vậy, các cột của ma trận kiểm tra tính 
chẵn lẻ đối với một mã như thế có độ dài 140 bit và bất kỳ tập lên tới 16383 của các cột này là một 
DLS 10. 
Bây giờ, chúng ta đặt câu hỏi liệu q  d đối với d  D đại diện cho một tập con các phần tử cho 
trước của V sao cho |q|  t. Theo quan niệm thảo luận trước đó, có thể nhận thấy câu hỏi là liệu đầu 
lớp tương ứng với q được phủ bởi đầu lớp tương ứng với d hay không. Chúng ta chứng tỏ có thể trả lời 
câu hỏi này, nhưng ở đây chúng ta yêu cầu một câu trả lời cài đặt nhanh, hiệu quả. Dựa vào (n - k) bộ 
sq đại diện cho q, chúng ta biết bất kỳ phần tử y trong lớp tương ứng với sq là một nghiệm thoả mãn 
yHT = sq . Dễ dàng sinh ra một nghiệm thoả mãn hệ này có (n - k) phương trình n ẩn, nhưng điều 
chúng ta yêu cầu là đầu lớp cq , là nghiệm có trọng số cực tiểu. Một cách có thể tìm được nghiệm này 
bằng cách sinh ra lớp từ bất kỳ nghiệm ban đầu, nghĩa là, tạo ra tổng nghiệm ban đầu lần lượt với mỗi 
một vector của mã và sau đó, tìm kiếm phần tử có trọng số cực tiểu - nhưng đây hầu như không phải là 
một thủ tục hiệu quả. Hơn nữa, một cách phải thực hiện tương tự đối với mỗi một sd và sau đó, so sánh 
mỗi một cd và cq . Chúng tôi đề xuất một cách tiếp cận trực tiếp hơn dựa vào bổ đề sau đây. 
 3
Bổ đề 1 
Cho cd và cq là các đầu lớp có trọng số  t đối với mã sửa lỗi nào đó. Cho w(x) là một hàm ánh 
xạ toàn không gian vector lên số nguyên như sau: w(x) = trọng số của đầu lớp (một phần tử có trọng 
số cực tiểu) trong lớp chứa x. Sau đó, cd  cq nếu và chỉ nếu: 
 w(cd  cq) + w(cq) = w(cd) (1) 
Chứng minh: 
Điều kiện cần là hiển nhiên. 
Đối với điều kiện đủ, giả sử w(cq) = trọng số của cq = x và w(cd) = trọng số của cd = y. Giả sử 
thêm cq  cd nhưng (1) có hiệu lực. Sau đó, lớp chứa (cd  cq) được dẫn bởi c0 nào đó có trọng số (y -
x). Nhưng bây giờ ((cd  cq)  c0) là một vector mã  0 và hơn nữa 
trọng số của ((cd  cq)  c0)  (x + y) + (y - x) 
  2(y) 
  2t 
là không thể có vì mã chứa các vector  0 có trọng số < (2t + 1). Như vậy, c0 không thể có trọng số (y 
- x) và bổ đề được chứng minh. 
Bây giờ, không có các đầu lớp cd và cq sẵn có cho chúng ta kiểm thử. Chúng ta có syndrome sd 
và sq thay thế và vì (cd  cq)HT = (cd HT)  (cq HT) syndrome của (cd  cq) mang tên (sd  sq). Tuy 
nhiên, không có vấn đề gì vì từ đó sự tương ứng giữa syndrome và lớp là 1-1, đó là vấn đề trực tiếp 
định nghĩa một hàm f(sx) = w(x). Điều này dẫn đến một dạng tương đương của (1): 
 f(sd  sq) + f(sq) = f(sd). 
III - THỦ TỤC TÌM KIẾM 
Từ bổ đề 1, rõ ràng bài toán tính toán chính trong tìm kiếm là xác định liệu f(sd  q) = f(sd) - f(sq). 
Về hai đại lượng, f(sd) và f(sq) có thể được tính dễ dàng (xem phần IV) và thường nhận được bằng 
cách đưa vào một thẻ ngắn là phần đại diện của tài liệu và truy vấn. Tuy nhiên, sự tính toán về f(sdq) 
phức tạp hơn. 
Theo thuật ngữ mã, tính toán f(sd  q) tương đương với tìm kiếm trọng số đầu lớp của một mảng 
chuẩn từ syndrome của lớp. Zieler và Prange đề xuất một phương pháp dựa vào lý thuyết nhóm. Về 
nguyên lý, phương pháp của họ làm việc đối với bất kỳ mã tuyến tính, nhưng khối lượng tính toán liên 
quan phụ thuộc nhiều vào các thuộc tính của mã riêng biệt khi xem xét. Các thủ tục hiệu quả tìm được 
đối với số mã có độ dài trung bình, bao hàm mã Golay. 
Như lựa chọn, chúng tôi coi bài toán tính toán f(sd  q) là một bài toán con của bài toán sửa lỗi. 
Cách tiếp cận rất hiệu quả đối với mã BCH, trong đó một lượng lớn các thủ tục sửa lỗi đã biết [2], 
[14], [18]. Một phương pháp nhận được từ quan niệm này được trình bày như sau. 
Một mã BCH đối với t sửa lỗi được định nghĩa bằng một bộ sinh đa thức g(x) sao cho: 
 G(i) = 0 i = 1, 3, ... , 2t - 1 
trong đó  là phần tử gốc của GF(2) đối với một mã có độ dài 2m - 1. Syndrome s của bất kỳ lỗi đa 
thức e(x) được cho bởi s = [ S1, S3 , ... , S2t - 1] , trong đó: Si = c(i) i = 1, 3, ... , 2t - 1 là tổng luỹ thừa. 
Tính toán f(sd  q) phải xác định trọng số có thể cực tiểu của e(x), mà syndrome của nó là sd  q . 
Định lí sau đây là thiết yếu đối với thủ tục của chúng tôi. 
Định lí Peterson [14] 
 4
Cho 











 10t260t250t2
1
40t2
2
30t2
3
1
20t2
4
2
0t
S
0
0
0
S
1
0
0
S
S
0
0
S
S
1
0
S
S
S
0
S
S
S
1
M







Sau đó, Mt0 là không suy biến nếu Si thuộc Mt0 là tổng luỹ thừa của t0 hoặc t0 - 1 các phần tử  0 
riêng biệt của GF(2m); Mt0 là suy biến nếu Si là tổng luỹ thừa của t0 - 2 hoặc ít hơn các phần tử  0 
riêng biệt của GF(2m). 
Theo định lí Peterson : nếu f(sd  q)  t thì f(sd  q) có thể được xác định bằng cách tính toán |Mt0| 
đối với t0 sao cho t0  t . Vì Si đã biết, | Mt0| có thể được tính dễ dàng đối với t0  t . Tuy nhiên, nếu f(sd 
 q) > t thì | Mt0| đối với bất kỳ t0  t không đưa ra một thông tin hữu ích nào. 
Cho u là giá trị lớn nhất của t0 (t0  t) sao cho | Mt0|  0. Chúng tôi trình bày một điều kiện cần 
đối với d để phủ q ở bổ đề sau đây. 
Bổ đề 2 
Cho f(sq)  0. 
Nếu f(sd  q) = f(sd) - f(sq) thì u = f(sd) - f(sq) + 1 (2) 
Chứng minh: 
Đối với bất kỳ trường hợp không tầm thường f(sq)  1; do đó, giả thiết được thoả mãn. Mặt 
khác, bằng bổ đề 1, f(sd  q) = f(sd) - f(sq) hàm ý d  q, lần lượt hàm ý f(sd  q)  f(sd) - 1  t - 1. Đối 
với bất kỳ e(x) có trọng số  t - 1, u - 1 = f(sd  q) là kết quả của định lí Peterson và bổ đề tiếp theo. 
Như vậy, (2) phải được thoả mãn nếu d phải phủ q. Các tài liệu này đối với nó (2) không có hiệu 
lực không phủ q và có thể không được để ý đến ngay tức thì. Bổ đề 2 có thể được dùng để sắp xếp ra 
ngoài hầu hết tài liệu không phủ q. 
Nhận xét 1: Đối với các hệ thống có thể chịu lỗi một số đáp ứng sai, bổ đề 2 cung cấp một tiêu 
chuẩn lựa chọn cho tìm kiếm. 
Lý thuyết mã cũng cung cấp một câu trả lời hoàn chỉnh đối với hệ thống cho phép không có đáp 
ứng sai nào. Khi cho rằng điều này kéo theo sự tính toán bổ sung nào đó. Xét phương trình 
 

u
1j
i
ji XS i = 1, 3, 5, ... , 2u - 1 (3) 
Đối với mã sửa t lỗi, (3) có thể được giải đối với Xi trong GF(2) nếu và chỉ nếu Si là tổng luỹ 
thừa của t hoặc ít hơn phần tử của GF(2). Kết quả, nếu (3) không thể giải được thì f(sd  q) > t. f(sd  q) 
> t hàm ý sự kiện q  d. Nếu (3) có thể giải được để sinh ra các phần tử riêng biệt u của GF(2) thì nếu 
a> u = t và 
b> tất cả phần tử u  0 thì f(sd  q) = t. Đây là trường hợp suy biến, đối với f(sd q) = t hàm ý f(sd) 
= t và f(sq) = 0. Cuối cùng, nếu (3) có thể được giải để sinh ra các phần tử riêng biệt và u  t - 1 thì d  
q. 
Chú ý: ở thảo luận trên sd q được giả thiết là  0. Khi sd q = 0 thì f(sd q) = 0 và d = q. 
Nghiên cứu thủ tục đề xuất kỹ lưỡng, rõ ràng ở đa số trường hợp u  f(sd) - f(sq) + 1 và do đó, 
thủ tục được kết thúc sau khi tính định thức. Dễ dàng nhận thấy quá trình tính định thức có thể được tổ 
chức theo cách sao cho ngay khi chúng ta biết định thức lớn nhất bằng 0 hay không, chẳng hạn, phép 
khử Gauss có thể được dùng, ma trận ở dạng thích hợp để giải nhanh (3). Các kỹ thuật giải (3) được 
 5
thảo luận ở các công trình về giải mã BCH [2], [14], [18]. Berlekamp [2] đề xuất một kỹ thuật biến đổi 
đơn giản làm giảm đáng kể khối lượng tính toán đòi hỏi khi giải (3). 
Thủ tục lựa chọn sau đây có thể được. Cho t1 = f(sd) - f(sq). Xét định thức |Mt1| . Nếu | Mt1| = 0 
thì theo bổ đề 1 và định lí Peterson, q  d. Nếu | Mt1|  0 thì có thể xác định định thức f(sd  q) bằng 
cách giải (3), với t1 thay cho u. Nói chung, không rõ ràng là thủ tục lựa chọn này có hiệu quả hơn thủ 
tục chính mô tả ở trên, nhưng nó dường như khá nhanh khi t1 nhỏ. 
Nhận xét 2: Điều kiện | Mt1|  0 là một điều kiện cần đối với d  q: do đó, nó có thể sử dụng là 
một tiêu chuẩn tìm kiếm ở hệ thống có thể chịu một số đáp ứng sai. 
IV - SƠ ĐỒ MÃ CÓ ĐỘ DÀI THAY ĐỔI 
Ở đây, chúng tôi mô tả một hệ thống tìm kiếm tài liệu sử dụng ý tưởng về mã có độ dài thay đổi 
để cực tiểu các yêu cầu hệ thống ở cả lưu trữ lẫn tính toán. 
Ở sơ đồ mã có độ dài thay đổi, độ dài syndrome của một vector tài liệu (vector truy vấn) có liên 
quan tới trọng số của nó wd (wq), trong đó 
 s = [S1, S2, ... , S2wd - 1] 
Tương tự đối với wq . Do đó, độ dài syndrome được sử dụng để tính trực tiếp trọng số của vector. 
Khi một truy vấn cho trước, chúng tôi muốn tìm kiếm tất cả tài liệu d sao cho d  q. Rõ ràng, 
chúng tôi phải có trọng số của vector tài liệu tối thiểu lớn bằng trọng số của truy vấn. Do đó, chỉ cần 
xét các tài liệu có syndrome dài hơn syndrome của truy vấn. Trường hợp có độ dài bằng nhau có thể 
chú ý chỉ bằng cách thử sd  q = 0. 
Khi wd > wq chúng tôi có thể tính từ syndrome truy vấn lấy tổng luỹ thừa bổ sung 
 S2wq+ 1 , S2wq+ 2 , ... , S2wd - 1 
theo bổ đề sau đây. 
Bổ đề 3 
Đối với một vector truy vấn có trọng số wq và bất kỳ wd > wq , các hàm 
 S2wq+ 1 , S2wq+ 2 , ... , S2wd - 1 
có thể được tính từ các hàm S1 , S2 , ... , S2wd - 1 
Chứng minh: 
Các đồng nhất thức Newton đối với GF(2) là 
S1 + 1 = 0 
S3 + 1S2 + 2S1 + 3 = 0 
. 
. 
. 
S2wd + 1 + 1 S2wd - 2 + ... + 2wd - 1 = 0 
Vì trọng số của vector truy vấn là wq 
 wq + 1 = wq + 2 = ... = 2wd - 1 = 0 
và bây giờ, các đồng nhất thức Newton trở thành 
S1 + 1 = 0 
S3 + 1S2 + 2S1 + 3 = 0 
. 
. 
. 
 6
S2wd - 1 + 1 S2wd - 2 + ... + wqS2wd - wq - 1 = 0 
Theo định lí Peterson, phương trình wq đầu tiên của hệ là độc lập tuyến tính và do đó, nó được 
sử dụng để giải đối với k (k = 1, 2, ... , wq). Phần còn lại của tổng luỹ thừa và k thuộc các phương 
trình cuối cùng wd - wq . 
Sau khi tổng luỹ thừa bổ sung được tính đối với truy vấn, thủ tục tìm kiếm ở phần III được áp 
dụng. 
Ưu điểm của cách tiếp cận mã có độ dài thay đổi là: 
1. Độ dài syndrome của mỗi một tài liệu được cực tiểu hoá, do đó, các yêu cầu lưu trữ được 
giảm. 
2. Lượng tính toán yêu cầu để xác định liệu một tài liệu d phủ truy vấn q cũng được giảm 
nhiều như bây giờ chúng tôi xử lý với syndrome có độ dài mwd đúng hơn là mt (t = Max{wd}). Lượng 
tính toán yêu cầu để nhận được tổng luỹ thừa S2wq+ 1 , S2wq+ 2 , ... , S2t - 1 là tương đối nhỏ hơn như nó 
được thực hiện chỉ một lần trong toàn bộ quá trình tìm kiếm về một truy vấn. 
3. Hệ thống hoàn toàn linh động vì không một mã riêng biệt nào cần được lựa chọn. Hệ thống 
chỉ tính toán một số đủ về tổng luỹ thừa để biểu diễn duy nhất một vector có một trọng số nhất định. 
Biểu diễn không làm thay đổi khi trọng số cực đại của vector tài liệu bị thay đổi. 
V- KẾT LUẬN 
Phương pháp tìm kiếm dựa vào mã đại số BCH trong thư viện số được trình bày ở bài báo này. 
Nó có hiệu quả trong tìm kiếm thông tin và không yêu cầu tính toán quá nhiều khi cài đặt. 
Nhận xét 3: Theo định lí Peterson, sự thêm các bộ mô tả mới vào hệ thống có thể thực hiện chỉ 
bởi thêm syndrome gốc vào syndrome tính toán chỉ từ các bộ mô tả mới. Nói riêng, nếu các bộ mô tả 
mới được thêm một mỗi lần, cập nhật syndrome đặc biệt trở nên đơn giản như i1i SS  đối với một 
vector có trọng số 1. 
Cuối cùng, chúng ta nhận xét về ưu điểm tương đối của kỹ thuật này so với các kỹ thuật khác 
đưa ra đối với bài toán như nhau. 
Nhận xét 4: Hai kỹ thuật cạnh tranh chính là 
a> mã chồng; 
b> biểu diễn tường minh của mỗi một tài liệu bằng một danh sách bộ mô tả. 
Ở trường hợp trước, thử nghiệm tìm kiếm là một trong số truy vấn n-bộ phải là tập con của 
chúng có n-bộ đối với bất kỳ tài liệu tìm kiếm và ở trường hợp sau, thử nghiệm kể cả đối với tập được 
cài đặt qua so sánh các danh sách bộ mô tả, tương ứng với tài liệu và truy vấn. 
Ở trường hợp mã chồng, thực tế hoặc logic trái với hoặc loại trừ (mod 2 cộng) không có một 
phép đảo duy nhất bắt buộc nó đúng là “tiến đến độ dài lớn” để nhận được tính giải mã được. Kautz và 
Singleton đề xuất một kỹ thuật đơn giản, chẳng hạn, yêu cầu một độ dài 525 bit để giải một bài toán 
cùng cỡ với ví dụ mô tả trước đây (t = 10, | V | = 15625). Như vậy, khi thử nghiệm tìm kiếm tầm 
thường, các yêu cầu lưu trữ lớn hơn nhiều đối với mã chồng. 
Sự so sánh với thao tác danh sách là dễ xử lý hơn nhiều. Độ dài của biểu diễn yêu cầu đối với 
hai phương pháp có thể so sánh được và ở đây, chúng tôi nhận thấy tính toán định thức cạnh tranh với 
các thao tác danh sách và so sánh. 
TÀI LIỆU THAM KHẢO 
1. W.Y. Arms - Digital Libraries, MIT Press, Cambridge, 2003. 
2. E.R. Berlekamp - Algebraic Coding Theory, Aegan Park Press, California, 1984. 
3. G. Birkhoff, S. MacLane - Tổng quan về đại số hiện đại, 2 tập, Nhà xuất bản Đại học và trung học 
chuyên nghiệp, Hà Nội, 1979. 
 7
4. Csiszar Imre, Korner Janos - Information Theory, Academic Press, Orlando, 1981. 
5. E.A. Fox - Advanced Digital Libraries, Virginia Polytechnic Institue and State University, 2000. 
6. J. von zur Gathen, J. Gerhard - Modern Computer Algebra, Cambridge University Press, 1999. 
7. R.A. Korfhage - Information Storage and Retrieval, John Wiley, New York, 1997. 
8. G. Kowalski - Information Retrieval Systems, Kluwer Academic Publishers, Boston, 1997. 
9. S. Lawrence, C. Lee Giles - Searching the World Wide Web, Science 280(3) (1998) 98-100. 
10. S. Lawrence, C. Lee Giles - Searching the Web: General and Scientific Information Access, IEEE 
Communications 37(1) (1999) 116-122. 
11. M. Lesk - Practical Digital Libraries, Morgan Kaufmann, San Francisco, 1997. 
12. C.T. Meadow - Text Information Retrieval Systems, Academic Press, San Diego, 1992. 
13. P. Perrin, F. Petry - An Information–theoretic based Model for Large-scale Contextual Text 
Processing, Information Sciences 116 (1999) 229-252. 
14. W.W. Peterson - Error-Correcting Codes, MIT Press, Cambridge, 1971. 
15. B.R. Schatz - Information Retrieval in Digital Libraries, Science 275 (1997) 327-334. 
16. J.C.A. Van der Lubbe - Information Theory, Cambridge University Press, 1997. 
17. C.J. Van Rijsbergen - Information Retrieval, 2nd Edition, Butterworths, London, 1979. 
18. Nguyễn Thuý Vân - Lý thuyết mã, xuất bản lần 2, Nhà xuất bản Khoa học và kỹ thuật, Hà Nội, 
2001. 
19. M.J. Wester - Computer Algebra Sytems, John Wiley, New York, 2000. 
20. I.H. Witten, D. Bainbridge - How to Build a Digital Library, Morgan Kaufmann, San Francisco, 
2003. 
SUMMARY 
AN METHOD OF INFORMATION RETRIEVAL 
BASED ON BCH CODES IN DIGITAL LIBRARIES 
Retrieval method based on BCH codes in digital libraries are presented in this paper. It is 
efficient in information retrieval and they do not require excessive computation in implemention. 
In Sections III, the retrieval procedure is discussed on basis of Theorem Peterson and binary 
BCH codes. We remark that by Lemma 1, addition of new descriptors to the system can be 
complished simply by addition of the original syndrome to the syndrome computed from the new 
desciptors only. 
For systems that can tolerate some false responses, Lemma 2 provides a selection criterion for 
retrieval. 
We remark that condition | Mt1|  0 is a necessary condition for d  q: hence, it can be used as 
the criterion for retrieval in systems that can tolerate some false responses. 
In Section IV, we describe a document retrieval system that utilizes the idea of varable length 
coding to minimize system requirements in both storage and computation. 
Finally, the two principal competing techniques appear to be a> superimposed coding and b> 
explicit representation of each document by a list of descriptors.