Thiết kế chatbot sử dụng thuật toán khoảng cách Levenshtein trên Raspberry

ng được sử 
 gồm 100 câu hỏi và 100 câu trả lời tương 
dụng hiện nay là thuật toán tính khoảng cách 
 ứng. Tập dữ liệu này được lấy từ tập dữ liệu 
Levenshtein. Thuật toán khoảng cách 
 huấn luyện nhưng lỗi ngẫu nhiên được thêm 
Levenshtein có thể áp dụng để so sánh cho hai 
 vào. Cụ thể chúng ta lấy 100 câu hỏi từ tập 
từ hoặc câu không cùng độ dài. Chatbot được 
 huấn luyện và cho phép sai ngẫu nhiên với số 
xây dựng dựa trên thuật toán Levenshtein và 
 từ sai nhỏ hơn hoặc bằng 2. Chúng ta gọi tập 
được triển khai trên máy tính nhúng 
 dữ liệu này là tập kiểm tra. Tập huấn luyện 
Raspberry Pi cho robot. 
 được mô tả trong bảng 1. 
2. ỨNG DỤNG THUẬT TOÁN 
 Bảng 1. Tập huấn luyện 
 KHOẢNG CÁCH LEVENSHTEIN 
 THIẾT KẾ CHATBOT Câu hỏi: Biến là gì 
 Thuật toán khoảng cách Levenshtein là Câu trả lời: Biến tượng trưng cho một ô 
một phương pháp để đánh giá mức độ giống nhớ để lưu trữ 
nhau giữa hai chuỗi [11]–[13]. Khoảng cách 
Levenshtein giữa hai từ hoặc câu là tính toán Câu hỏi: Kiểu dữ liệu số nguyên là kiểu nào 
số thay đổi nhỏ nhất để chuyển đổi từ hoặc Câu Trả lời: int, long, unsigned int, và 
câu này thành từ hoặc câu còn lại, dựa trên ba unsigned long 
phép biến đổi là: xóa, thêm, thay từng thành Câu hỏi: while và do while khác nhau thế nào 
phần trong từ hoặc câu [13]. Thuật toán 
khoảng cách Levenshtein cũng còn được biết Câu Trả lời: do while thực hiện ít nhất 1 
đến với tên gọi “khoảng cách chỉnh sửa” [12]. lần, while thì có thể không 
 Tạp Chí Khoa Học Giáo Dục Kỹ Thuật Số 61 (12/2020) 
 Trường Đại Học Sư Phạm Kỹ Thuật TP. Hồ Chí Minh 57 
 Độ dài lớn nhất cho các câu hỏi là 15 từ chúng tôi chọn giá trị ngưỡng là 2. Với giá trị 
không bao gồm các ký tự đặt biệt như dấu này, chương trình vẫn đảm bảo độ chính xác 
chấm hỏi. Các câu hỏi và câu trả lời được lưu khi có 2 từ trong câu hỏi không giống với câu 
trong cơ sở dữ liệu dưới dạng các tập tin định hỏi trong tập huấn luyện. 
dạng JSON (JavaScript Object Notation) với Lưu đồ chương trình tính khoảng cách 
từng cặp câu hỏi và câu trả lời. Các câu hỏi giữa 2 chuỗi được trình bày trong hình 1. 
và câu trả lời được phân biệt bằng ký tự đầu Trước hết chương trình sẽ điền giá trị chỉ 
tiên là “Q” cho câu hỏi và “A” cho câu trả mục vào hàng đầu tiên và cột đầu tiên. Sau 
lời. Với thư viện tiếng Việt, ta phải chuyển đó sẽ lần lượt tính giá trị các phần tử trong 
đổi các ký tự tiếng Việt sang bảng mã để ma trận sử dụng công thức Levenshtein (1). 
chương trình có thể dễ dàng nhận biết. Ví dụ 
 Kết thúc quá trình chúng ta thu được giá trị 
một cặp câu hỏi và câu trả lời được thể hiện thể hiện sự tương đồng của 2 chuỗi. 
trong cơ sở dữ liệu như bảng 2. 
 Bảng 2. Định dạng câu hỏi và câu trả lời 
 trong cơ sở dữ liệu 
 Câu hỏi và câu Câu hỏi và câu trả lời 
 trả lời bằng được mã hóa 
 tiếng Việt 
 "Q": " bi\u1ebfn l\u00e0 
 Biến là gì 
 g\u00ec " 
 "A": " Bi\u1ebfn 
 t\u01b0\u1ee3ng 
 Biến tượng 
 tr\u01b0ng cho 
 trưng cho một ô 
 m\u1ed9t \u00f4 
 nhớ để lưu trữ 
 nh\u1edb \u0111\u1ec3 
 l\u01b0u tr\u1eef " 
 Trong đó, câu hỏi là “Biến là gì” và câu 
trả lời là “Biến tượng trưng cho một ô nhớ để 
lưu trữ”. Theo đó, ký tự “ế” sẽ được lưu dưới 
dạng mã hex là \u1ebf, ký tự “à” sẽ là 
\u00e0, và tương tự cho các ký tự có dấu 
tiếng Việt còn lại. 
 Để tìm kiếm câu trả lời cho một câu hỏi 
trong cơ sở dữ liệu (CSDL), ta sử dụng thuật Hình 1. Lưu đồ giải thuật tính khoảng cách 
toán tính khoảng cách Levenshtein để so Levenshtein giữa hai chuỗi 
sánh mức độ giống nhau giữa câu hỏi được 
đưa ra và các câu hỏi có trong CSDL. Nếu Chương trình được viết bằng ngôn ngữ 
giá trị khoảng cách Levenshtein nhỏ hơn giá Python và thực thi trên hệ thống nhúng 
trị được cài đặt trước, trong bài báo này giá Raspberry Pi. Chuỗi đầu vào được lấy từ mô 
trị này bằng 2, thì hai chuỗi đó được xem là đun chuyển từ giọng nói sang văn bản và 
tương đồng nhau. Trong ứng dụng này chúng chuỗi còn lại được lấy từ cơ sở dữ liệu. 
ta lập trình tìm khoảng cách Levenshtein của Lưu đồ chương trình chính được mô tả 
2 chuỗi ở mức từ (word) thay vì ở mức ký tự trong hình 2. Câu hỏi nhận được từ mô đun 
(character). Nếu 2 chuỗi giống nhau, giá trị chuyển lời nói sang văn bản được so sánh với 
Levenshtein sẽ là 0. Ngược lại, giá trị đo tất cả các câu hỏi trong cơ sở dữ liệu. Lưu đồ 
được cho biết số từ khác nhau giữa 2 chuỗi. bài toán là giải thuật tìm lần so sánh có giá trị 
Bằng thực nghiệm trên tập dữ liệu nhỏ, nhỏ nhất và nhỏ hơn giá trị ngưỡng. Giá trị 
 Tạp Chí Khoa Học Giáo Dục Kỹ Thuật Số 61 (12/2020) 
 58 Trường Đại Học Sư Phạm Kỹ Thuật TP. Hồ Chí Minh 
ngưỡng được thiết lập trong biến MaxCost. robot di động. Để so sánh thời gian đáp ứng 
Giá trị cost ban đầu được khởi tạo là giá trị của thuật toán Levenshtein với các mạng học 
lớn nhất trong trường hợp 2 câu khác nhau sâu, tác giả thực thi 3 mô đun: thuật toán tìm 
hoàn toàn. Trong quá trình duyệt hết cơ sở dữ câu trả lời dựa trên Levenshtein, mạng nơ-
liệu, giá trị cost sẽ được cập nhật và câu hỏi ron tích chập (CNN), và mạng nơ-ron hồi qui 
có giá trị cost nhỏ nhất sẽ được lưu lại. được cải thiện (Long-short-term memory). 
 Mạng nơ-ron CNN và LSTM được thiết kế 
 sử dụng thư viện Keras. Các module được 
 thực thi trên phần cứng nhúng Raspberry Pi 
 để đo tốc độ đáp ứng khi đưa 10 câu hỏi ngõ 
 vào. Hệ thống nhúng Raspberry Pi 3 sử dụng 
 bộ xử lý ARM Cortex-A53 với bộ nhớ RAM 
 có dung lượng 1GB thích hợp cho các ứng 
 dụng di động như robot và các hệ thống tự 
 động điều khiển [17], [18]. 
 Chatbot sử dụng giải thuật khoảng cách 
 Levenshtein được so sánh với chatbot sử 
 dụng mạng CNN và mạng LSTM về thời 
 gian đáp ứng. Mạng CNN được thiết kế bao 
 gồm 1 lớp Convolution với hàm kích hoạt 
 ReLU, 1 lớp Maxpooling, 1 lớp kết nối đầy 
 đủ với 256 nơ-ron và 1 lớp ngõ ra với 100 
 nơ-ron để phân lớp. Các câu ngõ vào được 
 mã hóa sử dụng mã one-hot cho từng ký tự. 
 Mỗi ký tự được biểu diễn dưới dạng một 
 vector. Các vector của một câu tạo thành một 
 ma trận 2 chiều cho ngõ vào của mạng CNN. 
 Đối với mạng LSTM, sử dụng kiến trúc 
 Encoder-Decoder ở mức ký tự. Ngõ vào và 
 ngõ ra của mạng Encoder-Decoder cũng sử 
 dụng mã one-hot. 
 Đối với tập kiểm tra được tạo ra từ tập 
 huấn luyện, trong đó các câu sai ngẫu nhiên 
 0, 1, hoặc 2 từ. Độ chính xác của 3 mô hình 
 được liệt kê trong bảng 3. 
 Bảng 3. So sánh độ chính xác của chatbot sử 
 dụng thuật toán Levenshtein, mạng CNN và 
 mạng mạng LSTM. 
 Hình 2. Lưu đồ giải thuật tìm kiếm dựa trên 
 khoảng cách Levenshtein Levenshtein Mạng CNN LSTM 
3. KẾT QUẢ THỰC NGHIỆM VÀ 100% 99% 88% 
 THẢO LUẬN Đặc điểm của các mạng tích chập là cho 
 Mục đích sử dụng thuật toán khoảng kết quả tốt khi ngõ vào biến thiên nhẹ bởi các 
cách Levenshtein thay cho các mạng nơ-ron lớp maxpooling chỉ lấy kết quả lớn nhất trong 
là hướng đến một hệ thống nhỏ, gọn, có khả cửa sổ mà không quan tâm vị trí của phần tử 
năng thực thi tốt trên các hệ thống nhúng có lớn nhất. Trong khi đó mạng LSTM dựa trên 
cấu hình phần cứng thấp cho các thiết kế dự đoán các ký tự tiếp theo dựa trên các ký tự 
 Tạp Chí Khoa Học Giáo Dục Kỹ Thuật Số 61 (12/2020) 
 Trường Đại Học Sư Phạm Kỹ Thuật TP. Hồ Chí Minh 59 
hiện tại và trước đó lại cho ra sai số lớn khi Tính trung bình, chatbot sử dụng thuật toán 
ngõ vào thay đổi. Kỹ thuật so sánh dùng tìm kiếm khoảng cách Levenshtein nhanh 
Levenshtein khá đơn giản và trong trường hợp hơn 15 lần so với mạng CNN và 75 lần so 
sai số nhỏ có thể đảm bảo được độ chính xác với mạng LSTM. 
khá tốt. Với tập nhỏ và sai số đặc dưới mức Các chatbot hiện nay đa phần dựa vào 
ngưỡng thiết lập cho giải thuật thì chúng ta các mạng học sâu và xử lý ngôn ngữ tự 
vẫn đạt tỷ lệ 100%. Kết quả độ chính xác để nhiên, trong đó phổ biến là kiến trúc mạng 
kiểm chứng rằng đối với tập dữ liệu nhỏ và Long-Short-Term Memory. Kết quả của các 
cho ứng dụng robot trả lời một số câu có trong chatbot sử dụng các mạng nơ-ron cho kết quả 
kịch bản trước thì có thể sử dụng giải thuật tốt hơn, tìm kiếm chính xác và thông minh 
Levenstein thay cho các cấu trúc phức tạp như 
 hơn. Tuy nhiên để thực thi các mạng nơ-ron 
CNN và LSTM. Tỷ lệ nhận dạng của các CNN và mạng LSTM cần nhiều tài nguyên 
mạng phụ thuộc nhiều yếu tố như số nơ-ron, và thích hợp trên các máy tính có tốc độ xử 
số lớp mạng, các thông số cài đặt mô hình. lý cao và dung lượng lưu trữ lớn. Các mạng 
 Thời gian đáp ứng với mẫu thử là 10 câu CNN và LSTM khi được triển khai dưới các 
hỏi trong có trong CSDL của chatbot xây hệ thống nhúng có tài nguyên giới hạn sẽ 
dựng với thuật toán tìm kiếm dựa trên không hiệu quả. Trong khi đó, thực thi 
khoảng cách Levenshtein so với chatbot chatbot dựa trên giải thuật tìm kiếm 
được xây dựng với mạng nơ-ron CNN và Levenshtein đơn giản, sử dụng ít tài nguyên, 
LSTM được thể hiện trọng bảng 4. thích hợp với việc triển khai trên kiến trúc hệ 
 Bảng 4. So sánh thời gian đáp ứng của thuật thống nhúng nhỏ như Raspberry Pi. Như vậy 
 toán so sánh theo khoảng cách Levenshtein, việc xây dụng kỹ thuật tìm kiếm câu trả lời 
 mạng CNN và LSTM với Levenshtein đơn giản, tài nguyên còn lại 
 của hệ thống nhúng Raspberry có thể sử 
 Mô hình và thời gian đáp ứng (s) dụng cho các mục đích khác cho robot như 
 Mẫu xử lý ảnh ngõ vào, nhận dạng tiếng nói, và 
 Levenshtein Mạng CNN LSTM 
 thử quyết định, điều khiển ngõ ra. 
 1 0.001 0.303 1.3521 4. KẾT LUẬN 
 2 0.003 0.301 1.345 Chatbot được xây dựng trên thuật toán 
 tìm kiếm bằng khoảng cách Levenshtein có 
 3 0.005 0.301 1.342 
 thời gian phản hồi nhanh hơn 15 lần so với 
 4 0.007 0.310 1.534 mạng CNN và 75 lần so với LSTM. Các câu 
 5 0.028 0.309 1.432 hỏi và câu trả lời được thiết kế trước và lưu 
 vào cơ sở dữ liệu. Thuật toán tính khoảng 
 6 0.034 0.302 1.476 
 cách Levenshtein đơn giản, sử dung ít tài 
 7 0.024 0.300 1.421 nguyên và hiệu quả khi được thực thi trên hệ 
 8 0.026 0.302 1.486 thống nhúng Raspberry phục vụ cho việc 
 thiết kế các robot di động. Chatbot sử dụng 
 9 0.029 0.300 1.422 
 khoảng cách Levenshtein là một mô đun 
 10 0.034 0.305 1.496 trong thiết kế robot di động có khả năng giao 
 Thời gian gian đáp ứng của chatbot được tiếp với con người bằng giọng nói. 
xây dựng với thuật toán tìm kiếm dựa trên LỜI CẢM ƠN 
khoảng cách Levenshtein nhanh hơn so với 
 Kết quả nghiên cứu và ứng dụng là sản 
chatbot xây dựng bằng mạng CNN và mạng 
 phẩm của Đề tài Nghiên cứu Khoa học Cấp 
LSTM, khi có cùng số câu hỏi trong CSDL. 
 Bộ, mã số B2019-SPK-05, được hỗ trợ bởi 
Với những câu hỏi càng có nhiều từ trong 
 Bộ Giáo dục và Đào tạo và chủ trì bởi Trường 
câu thì chatbot sẽ càng mất nhiều thời gian 
 Đại học Sư phạm Kỹ thuật TP.HCM. 
để so sánh và tìm ra câu trả lời thích hợp. 
 Tạp Chí Khoa Học Giáo Dục Kỹ Thuật Số 61 (12/2020) 
 60 Trường Đại Học Sư Phạm Kỹ Thuật TP. Hồ Chí Minh 
 TÀI LIỆU THAM KHẢO 
[1] B. A. Shawar and E. Atwell, “Different measurement metrics to evaluate a chatbot 
 system,” in Proceedings of the workshop on bridging the gap: Academic and industrial 
 research in dialog technologies, 2007, pp. 89–96. 
[2] A. M. Rahman, A. Al Mamun, and A. Islam, “Programming challenges of chatbot: 
 Current and future prospective,” in 2017 IEEE Region 10 Humanitarian Technology 
 Conference (R10-HTC), 2017, pp. 75–78. 
[3] J.-C. Gu, Z.-H. Ling, and Q. Liu, “Utterance-to-Utterance Interactive Matching 
 Network for Multi-Turn Response Selection in Retrieval-Based Chatbots,” IEEE/ACM 
 Trans. Audio, Speech, Lang. Process., vol. 28, pp. 369–379, 2020. 
[4] B. Setiaji and F. W. Wibowo, “Chatbot Using a Knowledge in Database: Human-to-
 Machine Conversation Modeling,” in 2016 7th International Conference on Intelligent 
 Systems, Modelling and Simulation (ISMS), 2016, pp. 72–77. 
[5] G. M. D’silva, S. Thakare, S. More, and J. Kuriakose, “Real world smart chatbot for customer 
 care using a software as a service (SaaS) architecture,” in 2017 International Conference on I-
 SMAC (IoT in Social, Mobile, Analytics and Cloud) (I-SMAC), 2017, pp. 658–664. 
[6] M. Bates, “Health Care Chatbots Are Here to Help,” IEEE Pulse, vol. 10, no. 3, pp. 12–
 14, May 2019. 
[7] D. Madhu, C. J. N. Jain, E. Sebastain, S. Shaji, and A. Ajayakumar, “A novel approach for 
 medical assistance using trained chatbot,” in 2017 International Conference on Inventive 
 Communication and Computational Technologies (ICICCT), 2017, pp. 243–246. 
[8] A. Mondal, M. Dey, D. Das, S. Nagpal, and K. Garda, “Chatbot: An automated 
 conversation system for the educational domain,” in 2018 International Joint 
 Symposium on Artificial Intelligence and Natural Language Processing (iSAI-NLP), 
 2018, pp. 1–5. 
[9] M. Nuruzzaman and O. K. Hussain, “A Survey on Chatbot Implementation in Customer 
 Service Industry through Deep Neural Networks,” in 2018 IEEE 15th International 
 Conference on e-Business Engineering (ICEBE), 2018, pp. 54–61. 
[10] H. Honda and M. Hagiwara, “Question Answering Systems With Deep Learning-Based 
 Symbolic Processing,” IEEE Access, vol. 7, pp. 152368–152378, 2019. 
[11] A. Ene and A. Ene, “An application of Levenshtein algorithm in vocabulary learning,” 
 in 2017 9th International Conference on Electronics, Computers and Artificial 
 Intelligence (ECAI), 2017, pp. 1–4. 
[12] G. Navarro, “A guided tour to approximate string matching,” ACM Comput. Surv., vol. 
 33, no. 1, pp. 31–88, Mar. 2001. 
[13] V. I. Levenshtein, “Binary codes capable of correcting deletions, insertions, and 
 reversals,” in Soviet physics doklady, 1966, vol. 10, no. 8, pp. 707–710. 
[14] A. Andoni, R. Krauthgamer, and K. Onak, “Polylogarithmic Approximation for Edit 
 Distance and the Asymmetric Query Complexity,” in Proceedings - Annual IEEE 
 Symposium on Foundations of Computer Science, FOCS, 2010, pp. 244–252. 
[15] D. Q. Thang and P. T. Huy, “Determining restricted Damerau-Levenshtein editdistance 
 of two languages by extended automata,” in 2010 IEEE-RIVF International Conference 
 on Computing and Communication Technologies: Research, Innovation and Vision for 
 the Future, RIVF 2010, 2010. 
[16] K. U. Schulz and S. Mihov, “Fast string correction with Levenshtein automata,” Int. J. 
 Doc. Anal. Recognit., vol. 5, no. 1, pp. 67–85, Nov. 2002. 
[17] X. Wen and Y. Wang, “Design of smart home environment monitoring system based on 
 raspberry Pi” 2018 Chinese Control And Decision Conference (CCDC), Shenyang, 
 2018, pp. 4259-4263. 
 Tạp Chí Khoa Học Giáo Dục Kỹ Thuật Số 61 (12/2020) 
 Trường Đại Học Sư Phạm Kỹ Thuật TP. Hồ Chí Minh 61 
[18] S. Jain, A. Vaibhav and L. Goyal, “Raspberry Pi based interactive home automation 
 system through E-mail,” 2014 International Conference on Reliability Optimization and 
 Information Technology (ICROIT), Faridabad, 2014, pp. 277-280. 
Tác giả chịu trách nhiệm bài viết: 
TS. Trương Ngọc Sơn 
Trường Đại học Sư phạm Kỹ thuật TP.HCM 
Email: sontn@hcmute.edu.vn