Luận văn Ứng dụng phân hạng tổng hợp cho bài toán so khớp lược đồ

8 Chương 2- Một số thành tựu đạt được trong lĩnh vực so khớp lược đồ trả về một ánh xạ lược đồ So khớp lược đồ đã được tập trung nghiên cứu rất nhiều trong hai thập kỷ qua và đã có rất nhiều kỹ thuật được đề xuất để giải quyết bài toán này. Trong chương này, chúng ta tìm hiểu một số thành tựu đạt được trong lĩnh vực so khớp lược đồ, qua đó đánh giá những ưu điểm và hạn chế của từng công trình nghiên cứu. 2.1. Phát biểu bài toán so khớp lược đồ Lược đồ là một tập các phần tử có quan hệ với nhau, như tập các bảng, các cột trong lược đồ quan hệ hay các phần tử XML và các thuộc tính trong mô hình XML,…So khớp lược đồ là xác định sự tương ứng về ngữ nghĩa giữa các phần tử trong hai lược đồ khác nhau. Ví dụ 2.1 Cho hai lược đồ XML PO và Purchaseorder (là một phần lược đồ được trích từ hai lược đồ XML là PO và PurchaseOrder từ XCBL1 và được trình bày chi tiết trong PHỤ LỤC B) như sau: 1 www.xcbl.org 9 Hình 2.1- Hai lược đồ XML PO và PurchaseOrder Trong hai lược đồ ở Hình 2.1, hai phần tử PO.POShipTo và PurchaseOrder.DeliverTo tương ứng về ngữ nghĩa với nhau và được gọi là so khớp (match) với nhau vì chúng thể hiện cùng một khái niệm, đó là địa điểm (tên đường và thành phố) giao hàng của đơn đặt hàng tương ứng. Thao tác so khớp trong Hình 2.2 được định nghĩa như một hàm có dữ liệu vào là hai lược đồ S1, S2, và trả về một ánh xạ lược đồ . 10 Hình 2.2- Hàm so khớp lược đồ Một ánh xạ lược đồ là một tập các ánh xạ phần tử xác định các phần tử của hai lược đồ so khớp với nhau. Mỗi phần tử ánh xạ có thể có một biểu diễn ánh xạ thể hiện mối quan hệ giữa các phần tử của hai lược đồ quan hệ với nhau, biểu diễn ánh xạ có thể có hướng, hoặc vô hướng. Nó có thể sử dụng các quan hệ vô hướng (như =, ≤ ), các hàm (như hàm nối chuỗi,…), các mối quan hệ kiểu mô hình thực thể kết hợp (như “is-a”, “part-of”), các mối kết hợp hướng tập hợp (như chồng lắp, bao gồm),… Ví dụ 2.2 Trong hai lược đồ XML ở Hình 2.1, mỗi đường nối giữa một phần tử của lược đồ PO với một phần tử của lược đồ PurchaseOrder là một ánh xạ phần tử thể hiện mối quan hệ giữa chúng. Kết quả so khớp lược đồ là một ánh xạ lược đồ chứa tất cả các ánh xạ phần tử. Có rất nhiều công trình nghiên cứu cho bài toán so khớp lược đồ trả về một ánh xạ lược đồ, các công trình này đi theo nhiều hướng tiếp cận khác nhau, một số công trình tập trung nghiên cứu để cải thiện độ chính xác của các kỹ thuật so khớp cơ bản như các kỹ thuật so khớp dựa vào chuỗi, kỹ thuật so khớp dựa vào ngôn ngữ,… một số công trình nghiên cứu khác đi theo hướng tìm các chiến lược để kết hợp các thuật toán cơ bản lại với nhau. 2.2. Một số kỹ thuật so khớp lược đồ cơ bản Cho đến nay, có rất nhiều thuật toán đã được đề xuất và cài đặt để giải quyết bài toán so khớp lược đồ. Các thuật toán này thực hiện so khớp trên lược đồ dựa vào các kỹ thuật so khớp chuỗi, so khớp ngôn ngữ hoặc so khớp ràng buộc giữa các 11 phần tử của hai lược đồ và được gọi chung là các kỹ thuật mức phần tử, ngoài ra chúng có thể thực hiện so khớp ở mức cao hơn là mức cấu trúc của hai lược đồ. Các kỹ thuật so khớp mức cấu trúc ứng dụng các thuật toán đồ thị vào so khớp lược đồ để xem xét mức độ tương tự về cấu trúc giữa hai lược đồ (tương tự theo nghĩa hai cấu trúc này tương ứng về ngữ nghĩa với nhau). Trong một số công trình nghiên cứu, các thuật toán so khớp lược đồ còn sử dụng thêm thể hiện dữ liệu để thực hiện so khớp. Mỗi kỹ thuật so khớp có đầu vào là hai phần tử của hai lược đồ cần so khớp (như tên đối với so khớp chuỗi và ngôn ngữ, kiểu dữ liệu đối với so khớp ràng buộc,…) và trả về một giá trị thực thể trong khoảng [0,1] hiện mức độ tương ứng về ngữ nghĩa giữa hai phần tử này và được gọi là độ tương tự (similarity) giữa hai phần tử. Độ tương tự bằng 1 nghĩa là hai phần tử so khớp với nhau, độ tương tự bằng 0 nghĩa là hai phần tử này hoàn toàn không so khớp nhau, độ tương tự càng gần giá trị 1 thì mức độ tương ứng về ngữ nghĩa giữa hai phần tử càng cao, độ tương tự càng gần giá trị 0 thì mức độ tương ứng ngữ nghĩa giữa hai phần tử càng thấp. 2.2.1. Các kỹ thuật so khớp mức phần tử Các thuật toán so khớp lược đồ thường được bắt đầu bằng cách phát hiện những độ tương tự giữa các phần tử của hai lược đồ. Các kỹ thuật được sử dụng chủ yếu dựa vào tên các phần tử và những mô tả của các phần tử, và thường sử dụng kỹ thuật dựa vào chuỗi và dựa vào ngôn ngữ. 2.2.1.1. Các kỹ thuật so khớp dựa vào chuỗi Các kỹ thuật so khớp dựa vào chuỗi nhận đầu vào là hai chuỗi (tên hoặc mô tả tên của các phần tử của hai lược đồ) và trả về độ tương tự giữa hai chuỗi. Các kỹ thuật này đều dựa vào các kỹ thuật so khớp chuỗi trong lĩnh vực tìm kiếm thông tin (Information Retrieval) và được điều chỉnh để phù hợp với bài toán so khớp lược đồ. J. Euzenat và P. Shvaiko [12] đã tổng hợp một số công trình nghiên cứu về các kỹ thuật này. Những kỹ thuật này bao gồm so sánh chuỗi tiền tố (prefix), hậu tố 12 (suffix), so sánh chuỗi n-ký tự (n-gram), và kỹ thuật phức tạp hơn là khoảng cách biên tập (edit-distance) Tiền tố(hoặc hậu tố): Kỹ thuật này nhận đầu vào là hai chuỗi và kiểm tra chuỗi thứ nhất có phải là phần đầu (hoặc cuối) của chuỗi thứ hai không, nếu đúng thì trả về 1, ngược lại trả về 0. Ví dụ 2.3 So sánh hậu tố giữa hai chuỗi Count và ItemCount trả về giá trị 1. Chuỗi n-ký tự: Kỹ thuật này nhận đầu vào là hai chuỗi và tính số độ tương tự n-ký tự của chúng như sau: Cho n-ký tự (s, n) là tập các chuỗi con của s có chiều dài n. Độ tương tự n-ký tự được tính như sau: Gọi n-ký tự(s, n) là tập các chuỗi con của s có chiều dài, độ tương tự n-ký tự σ : S × S → R.sao cho: Ví dụ 2.4 3-gram của POLine là POL, OLi, Lin, ine và 3-n-gram của Items là Ite, tem, ems. Vậy độ tương tự 3-gram của POLine và Item là σ(POLine, Items) = 0. 3-gram của Item là Ite, tem, vậy σ(Item, Items) = 1 Khoảng cách biên tập: Có rất nhiều nghiên cứu về kỹ thuật này, mỗi nghiên cứu đề xuất một biến thể khác nhau của kỹ thuật cơ sở. Kỹ thuật khoảng cách biên tập được phát biểu như sau: cho một cặp chuỗi s và t, khoảng cách biên tập giữa hai chuỗi là một số thực r, giá trị của r thể hiện chi phí tối thiểu của một dãy các thao tác dùng để biến đổi chuỗi s thành chuỗi t, các thao tác gồm chèn, xóa và thay thế ký tự. Levenshtein đã đề xuất khoảng cách Levenshtein, khoảng cách này được tính bằng cách gán chi phí cho cả ba thao tác đều bằng 1. Nhóm tác giả Needleman và Wunsch đề xuất khoảng cách Needleman-Wunsch, trong đó thao tác chèn và xóa có 13 chi phí cao hơn thao tác thay thế ký tự. Một số các độ đo khác tính chi phí của các thao tác biên tập sử dụng một hàm với tham số là các ký tự hoặc các chuỗi con mà các thao tác này tác động lên, và chúng sử dụng một ma trận chi phí cho mỗi thao tác. Một trong những độ đo này là độ đo Smith–Waterman của nhóm tác giả Smith và Waterman, hay độ đo Monge-Eklkan của nhóm tác giả Monge và Elkan. Các kỹ thuật tính khoảng cách biên tập khác đã được đề xuất chủ yếu tập trung vào việc tìm các phương pháp tính chi phí hợp lý cho mỗi thao tác trong chuỗi thao tác để biến chuỗi s thành chuỗi t. Ví dụ 2.5 Chuỗi các thao tác biên tập để biến đổi chuỗi POLine thành Items gồm 2 thao tác thay thế ký tự (P I, Ot), 3 thao tác xóa ký tự (L, i, n), 2 thao tác chèn ký tự (m, s). Với mỗi kỹ thuật khác nhau, chi phí cho mỗi thao tác khác nhau và tính được khoảng cách biên tập khác nhau. Khoảng cách Levenshtein của hai chuỗi (POLine, Items) = 7 Tương tự, khoảng cách Levenshtein của hai chuỗi (Item, Items) = 1 2.2.1.2. Các kỹ thuật so khớp dựa vào ngôn ngữ Các kỹ thuật so khớp ngôn ngữ được phát triển theo nhiều hướng khác nhau như chun hóa về ngôn ngữ, sử dụng từ điển và hướng kết hợp hai phương pháp trên. J. Euzenat và P. Shvaiko [12] đã tổng hợp một số công trình nghiên cứu về các kỹ thuật này. Phương pháp chun hóa về ngôn ngữ (Linguistic normalisation): về mặt ngôn ngữ, cùng một từ có thể được biến thể dưới nhiều dạng khác nhau như biến tố (chẳng hạn thêm s vào sau các danh từ số nhiều), nguồn gốc của từ (như các danh từ được hình thành bằng cách thêm “ion” vào động từ hoặc các tính từ được hình thành bằng cách thêm “al” vào danh từ),…Do đó phương pháp chuNn hóa ngôn ngữ nhằm biến đổi các từ về dạng cơ bản của từ. Nhóm tác giả Maynard và Ananiadou phân biệt ba loại biến thể của từ là hình thái học (biến thể trên dạng và chức năng 14 của một từ dựa trên cùng một gốc), cú pháp (biến thể trên cấu trúc ngữ pháp của từ) và ngữ nghĩa (biến thể trên một thể (aspect) của từ, thường sử dụng từ khái quát hoặc từ chi tiết). Ví dụ 2.6 Từ theory paper có các biến thể về hình thái học như theory papers, theoretical paper, theoretical papers, các biến thể về cấu trúc ngữ pháp như paper on theory, philosophy and theory paper và các biến thể về ngữ nghĩa như foundational paper. Một loạt các phần mềm về chuNn hóa từ được xây dụng bởi Brill, chúng sử dụng những hàm sau để thực hiện chuNn hóa: • Tách từ (Tokenisation): Tên các thực thể được phân tích cú pháp thành dãy các từ đơn (token) bởi một bộ phân tích cú pháp thông qua việc nhận dạng dấu chấm câu, các chữ viết hoa, các ký tự trống, số,…( ItemNumber  , UnitOfMeasure  ). • Biến đổi về dạng cơ bản của từ (Lemmatisation): phân tích hình thái học các từ đơn để tìm các dạng cơ bản của từ. Lovins và Porter đã tập trung nghiên cứu các kỹ thuật biến đổi từ về dạng cơ bản gần đúng được gọi là kỹ thuật độn, trong đó các từ được loại bỏ phần hậu tố, ví dụ (Items Item). • Rút trích từ (Term extraction): Các nhóm tác giả Jacquemin và Tzoukermann, Bourigault và Jacquemin, Maynard và Ananiadou, và Cerbah và Euzenat đã đề xuất một số kỹ thuật rút trích từ từ một văn bản. Bộ rút trích từ nhận dạng từ thông qua sự lặp lại về hình thái của các đoạn tương tự và sử dụng các mẫu như danh từ 1 danh từ 2  danh từ 2 on danh từ 1, ví dụ theory paper cùng gốc với paper on theory. • Loại bỏ từ (Elimination): các thẻ token là các mạo từ, giới từ liên từ,…được đánh dấu để loại bỏ, như  . Sau khi ứng dụng các kỹ thuật chuNn hóa từ, tên hoặc mô tả tên của các phần tử được chuyển thành tập các từ ở dạng cơ bản, và có thể sử dụng các kỹ thuật dựa vào chuỗi để thực hiện so khớp. 15 Phương pháp sử dụng từ điển: Phương pháp này sử dụng từ điển để tìm những cặp tương tự. H. H. Do và E. Rahm [7] sử dụng từ điển từ đồng nghĩa và từ điển kiểu dữ liệu trong hệ thống COMA để thực hiện so khớp ngôn ngữ. Phương pháp kết hợp: kết hợp hai phương pháp trên lại với nhau để tăng độ chính xác so khớp. Phương pháp chun hóa từ được sử dụng trong giai đoạn tiền xử lý để biến đổi các cụm từ thành tập các từ ở dạng cơ bản, sau đó phương pháp sử dụng từ điển được ứng dụng để tìm độ tương tự giữa các từ ở dạng cơ bản này. J.Madhavan và các đồng sự [22] thực hiện chuNn hóa sử dụng các thao tác tách từ và thao tác loại bỏ từ, sau đó sử dụng từ điển gồm các dạng từ rút gọn (Qty tương ứng với Quantity), các từ viết tắt chữ cái đầu (UoM tương ứng UnitOfMeasure) và các từ đồng nghĩa (Bill and Invoice) để tìm ánh xạ phần tử trong hệ thống Cupid. F.Giunchiglia và các đồng sự [17], [18], [19] thực hiện chuNn hóa sử dụng các thao tác tách từ và thao tác biến đổi về dạng cơ bản của từ, sau đó sử dụng từ điển WordNet để rút trích ý nghĩa của các từ được chuNn hóa trong hệ thống S-Match. 2.2.1.3. Các kỹ thuật dựa vào ràng buộc Năm 2004, nhóm tác giả J. Euzenat và P.Valtchev [11] ứng dụng bộ so khớp ràng buộc trong hệ thống OWL-lite. Các lược đồ thường có các ràng buộc về khóa, kiểu dữ liệu, miền giá trị của các thuộc tính, các kiểu mối quan hệ, các bản số,…Nếu cả hai lược đồ đầu vào của thuật toán so khớp đều chứa thông tin như vậy, thuật toán so khớp ràng buộc có thể xác định các phần tử so khớp giữa hai lược đồ, như: hai phần tử tương tự nhau có thể được xác định dựa vào sự tương đương giữa kiểu dữ liệu và miền giá trị của các thuộc tính khóa (như các thuộc tính có ràng buộc duy nhất, các thuộc tính khóa chính, các thuộc tính khóa ngoại,…), có thể dựa vào bản số của mối kết hợp (như mối kết hợp 1:1,1:n, n:n) hay các mối quan hệ is-a. Kỹ thuật phổ biến nhất trong các kỹ thuật so khớp ràng buộc là so sánh kiểu dữ liệu. So sánh kiểu dữ liệu dựa vào ràng buộc kiểu dữ liệu của từng thuộc tính để tìm ra những cặp thuộc tính tương tự nhau. 16 Ví dụ 2.7 Thực hiện so khớp dựa vào ràng buộc kiểu dữ liệu cho hai lược đồ PO và PurchaseOrder trong ví dụ Hình 2.1. Kết quả trả về chia làm hai nhóm, nhóm thứ nhất gồm tất cả những ánh xạ phần tử giữa các phần tử có kiểu dữ liệu string của hai lược đồ, nhóm thứ nhất gồm tất cả những ánh xạ phần tử giữa các phần tử có kiểu dữ liệu int của hai lược đồ. Kết quả so khớp dựa vào ràng buộc kiểu dữ liệu không trả về những ánh xạ phần tử tương tự về ngữ nghĩa mà chỉ làm giảm số lượng các cặp phần tử cần so khớp (loại bỏ những cặp phần tử có một phần tử kiểu int và phần tử kia có kiểu string). Ngoài ràng buộc kiểu dữ liệu, các lược đồ quan hệ còn có các ràng buộc về khóa chính, khóa ngoại, hoặc các ràng buộc về miền giá trị của các thuộc tính, các kiểu mối quan hệ, các bản số,… Ví dụ 2.8 Trong bài báo [11], J. Euzenat và P.Valtchev đưa ra ví dụ về so khớp ràng buộc khóa như sau: Cho hai lược đồ SQL như trong Hình 2.3, lược đồ 1 gồm hai bảng Employee và Department, lược đồ 2 gồm một bảng Presonnel, thực hiện so khớp dựa vào kiểu dữ liệu và tên ràng buộc (ràng buộc khóa chính (primary key), ràng buộc tính duy nhất (unique), ràng buộc tham chiếu (references)…) 17 Lược đồ 1 Lược đồ 2 Employee EmpNo – int, primary key EmpName – varchar (50) DeptNo – int, references Department Salary - dec(15,2) Birthdate – date Personnel Pno - int, unique Pname – string Dept – string Born - date Department DeptNo – int, primary key DeptName – varchar (40) Hình 2.3 - Ví dụ về so khớp ràng buộc khóa So khớp lược đồ dựa vào kiểu dữ liệu và tên ràng buộc như sau: dựa vào kiểu dữ liệu, Born và Birthdate tương đương nhau; dựa vào kiểu dữ liệu, ràng buộc khóa chính và ràng buộc tính duy nhất, Pno tương đương với EmpNo và DepNo; Dựa vào kiểu dữ liệu string tương đương với varchar(n), Pname và DeptName có thể tương đương với EmpName và DeptName. 2.2.2. Các kỹ thuật so khớp mức cấu trúc E.Rahm và P. Bernstein [29] xem so khớp mức cấu trúc như là so khớp một kết hợp các phần tử của lược đồ này với một kết hợp các phần tử của lược đồ kia. Hiện nay, hầu hết các hệ thống so khớp đều sử dụng cấu trúc đồ thị để biểu diễn cấu trúc trong của lược đồ. Các nhóm nghiên cứu sử dụng đồ thị có hướng không chu 18 trình hoặc cây để biểu diễn lược đồ nhằm làm giảm độ phức tạp của bài toán. Tất cả các dự án nghiên cứu so khớp lược đồ gần đây đều dựa vào đồ thị, sử dụng khái niệm quan hệ láng giềng để tính độ tương tự cho từng phần tử. S. Melnik và các đồng sự [24] đã đề xuất phương pháp lan truyền độ tương tự trong hệ thống Similarity Flooding. M. Ehrig và S. Staab [10] đề xuất sử dụng thuật toán tìm kiếm láng giềng để tính độ tương tự giữa các phần tử. A. Madhavan và các đồng sự [22] đề xuất các thuật toán dựa vào mối quan hệ cha-con để tính độ tương tự giữa các phần tử của hai lược đồ. Ví dụ 2.9 Thực hiện so khớp cấu trúc dựa vào mối quan hệ cha-con để tính độ tương tự giữa các phần tử của hai cấu trúc con Line và Items của hai lược đồ PO và PurchaseOrder. PO PurchaseOrder Lines Item Line Qty UoM Items Item ItemNumber Quantity UnitOfMeasure Hình 2.4 - Hai cấu trúc con Lines và Items của hai lược đồ PO và PurchaseOrder So khớp giữa hai cấu trúc trong Hình 2.4 trả về một ánh xạ phần tử giữa Line và ItemNumber vì cha của chúng (Item) so khớp với nhau và hai con khác của Item là (Qty, Quantity) và (UoM, UnitOfMeasure) cũng so khớp nhau. Ví dụ 2.10 19 Thực hiện so khớp cấu trúc dựa vào mối quan hệ cha-con để tính độ tương tự giữa các phần tử của hai cấu trúc con ShipTo và DelieverTo của hai lược đồ PO và PurchaseOrder. PO PurchaseOrder POShipTo City Street POBillTo City Street DeliverTo Address Street City InvoiceTo Address Street City Hình 2.5 - Hai cấu trúc con ShipTo và DeliverTo của hai lược đồ PO và PurchaseOrder So khớp giữa hai cấu trúc trong Hình 2.5 trả về City và Street của POBillTo so khớp với City và Street của InvoiceTo hơn là của DeliverTo, vì Bill đồng nghĩa với Invoice nhưng không đồng nghĩa với Deliver. Một biến thể khác của các kỹ thuật so khớp mức cấu trúc được gọi là so khớp đường biên(Bounded path matching) do M. Ehrig và S. Staab đề xuất [10]. Kỹ thuật so khớp đường biên tính điểm tương tự giữa các cặp nút trên hai lược đồ bằng cách tìm tất cả các nút có nhãn giống nhau giữa hai lược đồ, sau đó tìm tất cả các cặp đường đi giữa hai cặp nút giống nhau trên hai lược đồ, và tính chiều dài của các cặp đường đi này (chiều dài của một đường đi bằng tổng số cung để đi từ nút này đến nút kia). Trên mỗi cặp đường đi có cùng chiều dài, những nút có cùng vị trí trên hai đường đi này được tăng độ tương tự lên một hằng số X. 20 2.2.3. Các kỹ thuật so khớp dựa vào các thể hiện dữ liệu và các kỹ thuật học máy K. Saleem và Z. Bellahsene [31] đã tổng hợp một số công trình nghiên cứu các kỹ thuật so khớp dựa vào thể hiện. Dữ liệu thể hiện trong so khớp lược đồ được sử dụng theo hai cách khác nhau. Cách thứ nhất được nhóm tác giả Bex, Neven và Vansummeren tập trung nghiên cứu cho trường hợp thông tin về lược đồ bị hạn chế hoặc thậm chí là không có (đối với lược đồ bán cấu trúc hoặc không có cấu trúc,…), khi đó so khớp thực hiện bằng cách sử dụng dữ liệu thể hiện để tạo ra một biểu diễn dữ liệu. Ví dụ, từ một tài liệu XML, kỹ thuật này thực hiện rút trích cấu trúc phân cấp dạng cây của các phần tử. Cách này còn được Hernedez và các đồng sự ứng dụng khi so khớp lược đồ có đầy đủ thông tin nhằm hỗ trợ trong việc tìm ngữ nghĩa của các phần tử. Cách thứ hai, so khớp lược đồ sử dụng các thể hiện dữ liệu để huấn luyện cho các thuật toán học máy. Các nút trong của lược đồ XML được A. Doan và các đồng sự thực hiện so khớp bằng cách so sánh các giá trị kết nối giữa các nút lá tương ứng của chúng sử dụng kỹ thuật máy học. Ví dụ 2.11 Thực hiện so khớp lược đồ dựa vào dữ liệu trên các bảng sau: 21 Hình 2.6 - Một ví dụ về so khớp dựa vào dữ liệu Kết quả so khớp dữ liệu trong Hình 2.6 trả về các ánh xạ phần tử (POBillTo.Street, DeliverTo.Street), (POBillTo.City, DeliverTo.City), (POShipTo.Street, InvoiceTo.Street), (POShipTo.City, InvoiceTo.City). 2.2.4. Nhận xét về các kỹ thuật so khớp cơ bản Các kỹ thuật so khớp chuỗi thường được cài đặt đơn giản. Tuy nhiên, so sánh chuỗi chỉ trả về kết quả tốt khi người thiết kế sử dụng những chuỗi rất tương tự nhau để chỉ cùng một khái niệm. Nếu những từ đồng nghĩa được sử dụng thì cặp chuỗi này sẽ được đánh giá với một độ tương tự rất thấp trong khi thật ra chúng rất tương tự nhau, ngược lại có những từ có nghĩa khác nhau nhưng được viết gần giống nhau. Trong so khớp lược đồ, mỗi lược đồ được thiết kế bởi những nhóm 22 thiết kế khác nhau, vì vậy các lược đồ sử dụng nhiều cụm từ khác nhau để biểu diễn cùng một khái niệm và cũng có thể sử dụng những cụm từ giống nhau để biểu diễn những khái niệm khác nhau. Vì vậy những kỹ thuật dựa vào chuỗi chỉ được sử dụng để phát hiện những chuỗi rất tương tự nhau. Ngược lại, so khớp phải sử dụng những kỹ thuật khác. Các thuật toán so khớp ngôn ngữ hiện nay đều sử dụng từ điển, so khớp dựa vào từ điển có thể phát hiện được từ đồng nghĩa, các từ tổng quát-chi tiết,..mà các kỹ thuật dựa vào chuỗi không thể phát hiện được. Từ điển là nguồn tài nguyên vô cùng quý trong so khớp lược đồ, chúng giúp các thuật toán nắm bắt ý nghĩa của các nhãn chính xác hơn. Tuy nhiên, cùng một từ trong từ đ