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

Nội dung text: Thiết kế chatbot sử dụng thuật toán khoảng cách levenshtein trên raspberry

1. 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 55 THIẾT KẾ CHATBOT SỬ DỤNG THUẬT TOÁN KHOẢNG CÁCH LEVENSHTEIN TRÊN RASPBERRY A CHATBOT USING LEVENSHTEIN DISTANCE ALGORITHM FOR RASPBERRY BOARD Trương Ngọc Sơn, Võ Thành Nhân, Lê Minh, Lê Minh Thành, Nguyễn Văn Phúc, Đặng Phước Hải Trang Trường Đại học Sư phạm Kỹ thuật TP.HCM, Việt Nam Ngày tòa soạn nhận bài 2/3/2020, ngày phản biện đánh giá 19/3/2020, ngày chấp nhận đăng 5/6/2020 TÓM TẮT Trong bài viết này, tác giả giới thiệu về thuật toán khoảng cách Levenshtein và ứng dụng thuật toán tìm kiếm dựa trên khoảng cách Levenshtein để thiết kế chatbot, thay thế cho các chatbot sử dụng mạng nơ-ron nhân tạo. Chatbot sử dụng thuật toán Levenshtein đơn giản và hiệu quả khi thực thi trên máy tính nhúng Raspberry cho các robot. Các thông tin được lưu trong cơ sở dữ liệu làm cơ sở cho chatbot trả lời câu hỏi từ người dùng. Để so sánh thời gian đáp ứng giữa chatbot sử dụng thuật toán tìm kiếm và chatbot sử dụng mạng nơ-ron, tác giả thiết kế mạng nơ-ron tích chập và mạng Long-Short-Term Memrory được huấn luyện với cùng tập dữ liệu. Các mô đun được thực thi trên hệ thống nhúng Raspberry. Kết quả thực nghiệm cho thấy, chatbot sử dụng thuật toán tìm kiếm dựa trên khoảng cách Levenshtein có thời gian đáp ứng nhanh với cùng độ chính xác cho các câu hỏi có trong cơ sở dữ liệu. Kiểm tra trên 10 câu hỏi ngẫu nhiên, chatbot sử dụng thuật toán Levenshtein cho kết quả nhanh hơn 15 lần so với dùng mạng CNN và 75 lần so với dùng mạng LSTM. Chatbot sử dụng giải thuật Levenshtein là một ứng dụng tối ưu nhằm làm giảm tối đa tài nguyên cho các máy tính nhúng có kiến trúc thấp được sử dụng trong các robot di động. Từ khóa: Chatbot; Khoảng cách Levenshtein; Thuật toán tìm kiếm; Mạng nơ-ron; Mạng nơ- ron tích chập. ABSTRACT In this paper, we present a chatbot based on the Levenshtein Distance for low-cost embedded systems. The state-of-the art chatbots are based on deep neural networks, however, such chatbots cannot be deployed on the low-cost embedded system, such as Raspberry board for mobile robots. Chatbot based on Levenshtein Distance requires fewer resources and can be deployed on low-cost embedded systems efficiently. The Levenshtein distance represents the similarity between the two strings. The similarity between the input question and all the stored questions in the database are measured. A winner is a stored question that is the best similar to the input question. Having recognized the question, chatbot can decide the output by querying from the database. Chatbot using (a) search algorithm based on Levenshtein distance is faster by 15 times and 75 times than the Convolutional Neural Network and the LSTM network. The chatbot based on Levenshtein Distance is suitable to be deployed on the low-cost embedded systems for mobile robots. Keywords: Chatbot; Levenshtein distance; Search algorithm; Neural network; Convolutional neural networks; đưa ra câu trả lời hoặc các quyết định khi 1. GIỚI THIỆU người dùng truy vấn [4]. Với chatbot, người Chatbot là một phần mềm hỗ trợ giao tiếp dùng có thể giao tiếp với các hệ thống bằng giữa người và máy [1]–[3]. Các chatbot được ngôn ngữ tự nhiên (natural language) mà cài đặt một lượng thông tin và có khả năng không cần phải sử dụng các ngôn ngữ lập
2. Tạp Chí Khoa Học Giáo Dục Kỹ Thuật Số 61 (12/2020) 56 Trường Đại Học Sư Phạm Kỹ Thuật TP. Hồ Chí Minh trình phức tạp. Chatbot đóng vai trò như một Công thức toán học của thuật toán trợ lý ảo, có thể được sử dụng trong nhiều lĩnh khoảng cách Levenshtein giữa hai chuỗi a và vực khác nhau như kinh doanh, y tế và cả b [14]–[16]: trong giáo dục [5]–[8]. Các chatbot hiện nay max( i, j)if min(i, j) 0 được xây dựng chủ yếu sử dụng các mạng nơ- ron nhân tạo, trong đó chủ yếu là các mạng leva,b (i 1, j) 1 leva,b (i, j) (1) học sâu (deep leanring) [9], [10]. Mặc dù các min leva,b (i, j 1) 1 otherwise mạng học sâu cho kết quả khá tốt nhưng nó lev (i 1, j 1) 1 a,b (ai bi ) chỉ thực sự phát huy hiệu quả khi được thực Trong đó, 1 bằng 0 khi ≠ và bằng thi trên các máy tính có cấu hình mạnh bởi vì ( 푖≠ 푗) 푖 푗 các mạng học sâu dựa trên một số lượng lớn 1 trong các trường hợp còn lại. 푙푒푣 , (푖, 푗) là các phép toán, xử lý, và các thông số mô hình. khoảng cách giữa i ký tự đầu tiên của chuỗi a Khi triển khai các mạng học sâu cho các thiết và j ký tự đầu tiên của chuỗi b. bị nhỏ như các robot chúng ta gặp nhiều khó Chatbot được trình bày trong bài báo này khăn. Các hệ thống nhúng ngày nay mặc dù là một ứng dụng trong robot trợ lý giảng dạy. có khả năng thực thi các mạng học sâu, tuy Chatbot được cài đặt các câu hỏi và câu trả nhiên nó luôn bị hạn chế về tốc độ và khả lời liên quan đến một môn học cụ thể. Chúng năng lưu trữ. Trong các ứng robot cần phần tôi chọn môn Ngôn ngữ lập trình C với các cứng nhỏ gọn nhưng vẫn đáp ứng yêu cầu về kiến thức cơ bản làm nội dung cài đặt cho độ chính xác và tốc độ đáp ứng. Đối với các chatbot. Tập dữ liệu được tạo với 100 câu hỏi tập dữ liệu nhỏ, chúng ta có thể sử dụng các và 100 câu trả lời tương ứng. Tập dữ liệu này thuật toán so sánh để thiết kế chatbot thay cho được dùng để cài đặt cho chatbot. Tập dữ các mạng học sâu nhằm tăng độ chính xác và liệu này cũng được sử dụng để huấn luyện thời gian đáp ứng. Các thuật toán so sánh sẽ cho mạng nơ-ron tích chập và mạng nơ-ron đánh giá mức độ giống nhau giữa câu hỏi hồi quy để so sánh kết quả. Chúng ta có thể người dùng đưa ra và các câu hỏi có trong cơ gọi tập dữ liệu này là tập huấn luyện. Đối với sở dữ liệu (CSDL), từ đó đưa ra câu trả lời tập dữ liệu phục vụ cho việc đánh giá mô phù hợp được cài đặt trước. Và một trong hình, chúng tôi cũng tạo một tập dữ liệu bao những thuật toán so sánh thườ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
3. 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ị
4. 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ự
5. 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.
6. 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.
7. 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