MỤC LỤC
Chương 1 Mở đầu . 1
1 Đối sánh lược đồ 2
2 Sự hỗn tạp ngữ nghĩa .3
3 Định nghĩa bài toán 6
3.1 Schemas 6
3.2 Đầu vào bài toán (Input) 7
3.3 Đầu ra bài toán (Output) 7
3.4 Kiến trúc chung 8
4 Ứng dụng của bài toán đối sánh lược đồ 9
4.1 Các ứng dụng tích hợp dữ liệu và data warehouse 9
4.2 E-Business . 11
4.3 Semantic Web 12
5 Các vấn đề mở 13
5.1 Khả năng biểu diễn của ngôn ngữ 13
5.2 Làm việc với các lược đồ có kích thước lớn 13
5.3 Sự kết hợp của các phương pháp đối sánh 14
Chương 2 Các phương pháp tiếp cận . 15
1 Các dự án liên quan . 15
1.1 COMA++ . 15
1.2 SEMINT . 16
1.3 LSD 16
1.4 SKAT . 16
1.5 TransScm 16
1.6 DIKE . 17
1.7 SIMILARITY FLOODING 17
1.8 Cupid 17
2 Các phương pháp đối sánh lược đồ . 20
2.1 Tiêu chuẩn phân loại . 20
2.2 Đối sánh dựa trên schema (schema-based) 21
2.2.1 Phương pháp tiếp cận dựa trên ngôn ngữ (linguistic) 22
2.2.2 Phương pháp tiếp cận dựa trên ràng buộc . 23
2.2.3 Phương pháp tiếp cận dựa trên cấu trúc . 23
2.3 Đối sánh dựa trên dữ liệu . 23
2.4 Đối sánh kết hợp . 24
2.5 Match Cardinality 24
2.6 Các hệ số mặc định trong bài toán đối sánh 25
3 Các phương pháp đánh giá hệ thống đối sánh 26
Chương 3 Thiết kế hệ thống đối sánh lược đồ. 30
1 Khảo sát . 30
2 Giới thiệu . 33
2.1 Giới thiệu bài toán đối sánh lược đồ. 33
2.2 Xử lý schema trong tiếng Việt . 33
3 Thiết kế 35
3.1 Kiến trúc hệ thống 35
3.2 Input 36
3.2.1 Schema 38
3.2.2 WordNet 39
3.2.3 Output 40
3.3 Mức ngôn ngữ (linguistic matching) . 41
3.3.1 Các thuật toán đối sánh cơ bản . 42
3.3.2 Thuật toán đối sánh kết hợp . 44
3.4 Mức cấu trúc 51
3.5 Chọn lựa ánh xạ . 55
4 Cài đặt và kết quả . 56
4.1 Cài đặt 56
4.2 Kết quả thử ngiệm 60
5 Kết luận và hướng phát triển . 71
5.1 Kết luận 71
5.2 Hướng phát triển 72
Tài liệu tham khảo . 75
Sách, bài báo, luận văn 75
Website . 75
85 trang |
Chia sẻ: maiphuongtl | Lượt xem: 1630 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu Luận văn Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng vnmatch, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Org_Sender.
• Từ được viết gọn lại: Ví dụ Org có nghĩa là Organization.
• Từ có nhiều nghĩa.
23
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
2.2.2 Phương pháp tiếp cận dựa trên ràng buộc
Các lược đồ thường chứa các thông tin ràng buộc như size, data type, key,
range, unique… cho mỗi phần tử. Nếu các thông tin này xuất hiện trong cả hai
lược đồ thì nó sẽ được khai thác để ước lượng độ tương đồng. Ví dụ có thể tính
toán độ tương đồng giữa hai phần tử dựa trên data type, key…
Đối với các thông tin này, cách tiếp cận chung là tạo một bảng trong đó chứa hệ
số tương tự của các ràng buộc. Ví dụ như kiểu String và kiểu varchar là hoàn toàn
tương tự nhau.
2.2.3 Phương pháp tiếp cận dựa trên cấu trúc
Phương pháp tiếp cận này khai thác các quan hệ giữa các phần tử và đối
sánh kết hợp các phần tử xuất hiện trong cùng một cấu trúc. Phụ thuộc vào các
ngôn ngữ mô tả lược đồ khác nhau mà có các kiểu quan hệ giữa các phần tử khác
nhau. Ví dụ như các quan hệ is-a/part-of, hoặc các ràng buộc tham chiếu. Thông
thường lược đồ được biểu diễn dưới dạng đồ thị (có hướng hoặc vô hướng). Để
xác định độ tương đồng giữa các phần tử người ta thường sử dụng khái niệm
phần tử hàng xóm (element neighborhood) để hạn chế phạm vi khi so sánh các
phần tử.
2.3 Đối sánh dựa trên dữ liệu
Phương pháp này duyệt qua các bản ghi dữ liệu để xác định sự tương ứng
và được chọn khi các thông tin trong lược đồ bị giới hạn hoặc trong trường hợp dữ
liệu được biểu diễn dưới dạng bán cấu trúc. Trong trường hợp đặc biệt không có
lược đồ người ta phải xây dựng nó từ các dữ liệu đã có, trường hợp này người ta
phải sử dụng các kỹ thuật được gọi là trích lọc lược đồ. Ngay cả khi có lược đồ thì
thông tin về dữ liệu cũng có thể được xem xét để tăng khả năng khai thác ngữ
nghĩa trong lược đồ
Đối với phương pháp này, kích thước dữ liệu đầu vào bài toán lớn hơn
nhiều so với lược đồ nên thời gian thực hiện đối sánh cũng là một trong những
vấn đề cần quan tâm.
24
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
2.4 Đối sánh kết hợp
Đối sánh chỉ sử dụng một phương pháp tiếp cận sẽ không thích hợp để cho
ra một kết quả tốt với sự đa dạng của lược đồ. Vì vậy hầu hết các hệ thống đối
sánh lược đồ hiện tại đều kết hợp sử dụng nhiều phương pháp đối sánh. Đối sánh
kết hợp có thể được thực hiện theo hai cách khác nhau là hybrid hoặc composite.
Hybrid tích hợp nhiều cách tiếp cận vào trong engine trong khi composite kết hợp
kết quả của nhiều cách tiếp cận độc lập lại với nhau. Trong hầu hết các hệ thống
có sử dụng đối sánh lược đồ đều sử dụng đối sánh kết hợp (Cupid)
2.5 Match Cardinality
Kết quả đối sánh giữa hai lược đồ S1 và S2 là tập các co-element giữa các
phần tử của nó, một phần tử S1 (S2) có thể tồn tại trong nhiều co-element. Hơn
nưa, một hay nhiều phần tử S1 có thể tương đương với một hoặc nhiều phần tử
của S2. Vì vậy chúng ta có các quan hệ về số lượng 1:1. 1:n, n:1, m:n .
Cardinality s (S1) t (S2)
1:1 Price Cost Price=Cost
n:1 FirstName,
LastName
Name Concat(FirstName,
LastName) = Name
1:n Name FirstName,
LastName
Split(Name) =
{FirstName, LastName}
m:n P.PersName,
P.DeptNoD.DeptNo,
D.DeptName
A.Person,
A.Department
SELECT P.PersName,
D.DeptNameFROM P, D
WHERE
P.DeptNo=D.DeptNo =
{A.Person,
A.Department}
Bảng 1: Đối sánh dựa trên số lượng phần tử
25
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
2.6 Các hệ số mặc định trong bài toán đối sánh
Trong các phương pháp đối sánh đã trình bày ở trên trong các dự án cụ thể
đều có sử dụng các hệ số mặc định để chỉ ra sự tương tự giữa các phần tử theo
các tiêu chí đặc biệt. Ví dụ bảng hệ số tương tự giữa các phần tử khi so sánh các
kiểu dữ liệu của chúng với nhau, với tiêu chí này người ta không xây dựng bất cứ
thuật toán nào mà thường sử dụng các hệ số được định nghĩa sẵn. Ngoài ra còn
các hệ số mặc định để chỉ ra độ ưu tiên của một thuật toán so với thuật toán
khác, ví dụ độ ưu tiên của mức ngôn ngữ so với độ ưu tiên của mức cấu trúc.
Type(s) Type(t) Datatype_match(s,t)
string string 1.0
string date 0.2
decimal float 0.8
float float 1.0
float integer 0.9
… … …
Có một số phương pháp để xây dựng bảng hệ số như trên nhưng phương
pháp thường được các chuyên gia sử dụng là dựa vào thực nghiệm. Quá trình xây
dựng các hệ số được thực hiện theo các bước sau:
1. Thực hiện đối sánh bằng tri thức chuyên gia, được kết quả là một tập hợp
các ánh xạ giữa các phần tử của hai lược đồ Sexp kết quả thực tế mà bài
toán cần hướng tới).
2. Thực hiện đối sánh tự động với hai lược đồ và cũng thu được tập hợp các
ánh xạ giữa các phần tử của hai lược đồ Sauto.
3. Sẽ có sự khác nhau giữa tập hợp ánh xạ do chuyên gia và tập ánh xạ do
máy thực hiện. Các hệ số Wdefault sẽ được điều chỉnh sao cho tập Sauto giống
với tập Sexp nhất có thể.
26
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
Hình 2-3: Xây dựng các hệ số ưu tiên
Các hệ số thu được có thể được áp dụng cho nhiều bài toán khác nhau,
thuật toán khác nhau.
3 Các phương pháp đánh giá hệ thống đối sánh
Để đánh giá kết quả của các hệ thống đối sánh lược đồ chúng ta có thể sử
dụng các phương pháp sau đây
1. So sánh kết quả đối với kết quả đối sánh của các chuyên gia. Đây là một
phương pháp khá hiệu quả và nó thường được sử dụng để xây dựng các hệ
số ưu tiên trong các thuật toán đối sánh. Các hệ số được điều chỉnh sao
cho kết quả tự động bằng máy với kết quả của chuyên gia giống nhau
nhất. Thực hiện với nhiều lược đồ sẽ thu được các hệ số thực nghiệm tối ưu
nhất.
2. So sánh kết quả đối sánh với kết quả của các hệ thống khác.
3. Đánh giá tự động: Ký hiệu B là tập các ánh xạ đúng (ánh xạ đúng là ánh
xạ do chuyên gia thực hiện), C: Tập các ánh xạ sai, A tập ánh xạ đúng
27
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
nhưng không được thuật toán tìm thấy và D là tập ánh xạ sai được thuật
toán loại bỏ
Hình 2-4: Đánh giá hệ thống đối sánh
Ta có hai công thức sau để ước lượng hiệu quả của thuật toán đối sánh
• Cho biết sự tin cậy của thuật toán đối sánh
Precision=
CB
B
+ ,
• Cho biết phần trăm của các ánh xạ hợp lệ (có giá trị)
Recall=
AB
B
+
Khi tập A và tập C không tồn tại thì Precision và Recall có giá trị 1. Tuy
nhiên một giá trị Recall hoặc Precision thì không thể ấn định được chất lượng của
thuật toán đối sánh.
Như vậy cần phải xem xét các phương pháp kết hợp hai giá trị trên đối lại
với nhau. Có một số phương pháp kết hợp đã được xây dựng sau
1. FMeasure(α ) được mô tả trong [9]:
FMeasure(α )=
recallprecision
recallprecision
CBA
B
**)1(
*
**)1( αααα +−=++−
Trong đó 0<α <1 cho phép các giá trị thể hiện sự quan trọng khác nhau
đối với Precision và Recall. FMeasure(α ) hội tụ về Precision khi α =1 và hội tụ về
Recall khi α =0
28
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
2. FMeasure : Khi Precision và Recall được xem có độ quan trọng bằng nhau
ta có công thức sau
FMeasure=
recallprecision
recallprecision
CBBA
B
+=+++
**2
*2
3. Overall: Đây là công thức được nêu trong [10] và công thức này được
nhắm vào chính các ứng dụng đối sánh lược đồ
Overall= )12(*1
precision
recall
BA
CB
BA
CA −=+
−=+
+−
Để so sánh hai phương pháp FMeasure và Overall ta có hình sau. Nhìn vào
đồ thị ta thấy FMeasure tối ưu hơn so với Overall. Với cùng giá trị của Precision
và Recall thì FMeasure cao hơn so với Overall. Overall nhạy cảm với biến
Precision hơn. Khi Precision=0,5 thì Overall=0;
Hình 2-5: So sánh F-Measure và Overall
29
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
30
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
Chương 3 Thiết kế hệ thống đối sánh lược đồ.
1 Khảo sát
Hiện nay các công ty, tổ chức đều có các cơ sở dữ liệu chưa các thông tin
quản lý, tác nghiệp điều hành. Đối với các công ty, hoặc các tổ chức có qui mô
lớn, dữ liệu phân tán trên cả mặt logic và vật lý. Các tổ chức này thường dùng
các hệ quản trị cơ sở dữ liệu và hệ thống phần mềm khác nhau để quản lý cơ sở
dữ liệu, điều này dẫn đến việc tích hợp dữ liệu các cơ sở dữ liệu này thành một
thể thống nhất gặp rất nhiều khó khăn vì sự hỗn tạp của dữ liệu.
Các hệ thống cơ sở dữ liệu thường được dùng bao gồm: Lotus notes, MS
SQL Server, Oracle, MySQL. Trong hình dưới đây minh họa sự hỗn tạp của các
nguồn dữ liệu văn bản, đây là một mô hình đang được áp dụng trong các tổ chức
ở Việt Nam hiện nay.
31
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
Organization 3Organization 2Organization 1
Domino SQL server Oracle
Schema1 Schema2 Schema3
E-docman
App
E-docman
App
E-docman
App
Mediator
Local schemaLocal schema
Global schema
Query Result
Hình 3-1: Sự hỗn tạp của các nguồn dữ liệu
Hiện tại nhu cầu về bài toán tích hợp dữ liệu (Data integration) hoặc
chuyển đổi dữ liệu (Data translation) một cách tự động hoặc bán tự động là thực
sự cần thiết. Trên thực tế các công ty hay tổ chức hiện nay khi xây dựng các ứng
dụng có sử dụng dữ liệu đã có sẵn thì thường phải xây dựng một công cụ với các
thao tác thủ công (manual) để tiến hành chuyển đổi hoặc tích hợp dữ liệu cũ vào
ứng dụng mới. Những thao tác thủ công sẽ không lợi ích về mặt kinh tế cũng như
32
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
quá trình xử lý sẽ xuật hiện các lỗi thao tác bằng tay. Như vậy người ta cần phải
xây dựng các mô hình tự động hoặc bán tự động cho bài toán này để giảm thiểu
tối đa các thao tác thủ công.
33
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
2 Giới thiệu
Trong hình dưới đây là hai lược đồ về cơ sở dữ liệu văn bản. chúng ta có
thể nhận ngay ra các xung đột trong hai lược đồ này. Vấn đề đặt ra bây giờ là xử
lý các xung đột đó một cách tự động nhiều nhất các thao tác có thể.
Hình 3-2:Lược đồ văn bản
2.1 Giới thiệu bài toán đối sánh lược đồ.
Đối sánh (Match) là thao tác xử lý 2 lược đồ đầu vào và cho đầu ra một
ánh xạ các phần tử phù hợp giữa hai lược đồ. Đối sánh lược đồ là bước khó trong
nhiều ứng dụng: Trong Thương mại điện tử, trợ giúp ánh xạ các message giữa
các định dạng XML khác nhau, trong Datawarehouse, giúp ánh xạ dữ liệu nguồn
vào trong các lược đồ của Warehouse…
2.2 Xử lý lược đồ trong tiếng Việt
Trên thực tế trong các ứng dụng về cơ sở dữ liệu ở Việt Nam hiện nay, có
rất nhiều các lược đồ được thiết kế sử dụng tiếng Việt, các thuộc tính định danh
(identify name) thường sử dụng tiếng Việt không dấu để biểu diễn, còn các các
mô tả thuộc tính có thể là tiếng Việt có dấu hoặc không có dấu. Ngoài ra các lược
đồ này còn kết hợp cả tiếng Anh, như vậy việc xử lý các lược đồ này còn gặp rất
34
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
nhiều khó khăn do có quá nhiều các xung đột về ngữ nghĩa, từ vựng, sự hạn chế
của các giải thuật xử lý ngôn ngữ cho tiếng Việt …
Dựa trên những thuật toán xử lý cho các thứ tiếng khác ta cũng hoàn toàn có thể
xây dựng được thuật toán xử lý cho tiếng Việt, nếu ta có được các bộ từ điển như
tiếng Anh.
Tôi đề xuất một vài phương pháp tiếp cận cho tiếng Việt trong bài toán đối sánh
lược đồ có thể sử dụng trong đối sánh ngôn ngữ
1. Nếu ta xây dựng được một từ điển phân loại (taxonomy) giống như
Wordnet3 cho tiếng Việt, chúng ta hoàn toàn có thể thực hiện các thuật
toán đối sánh như trong tiếng Anh. Có thể xem một trong những thuật
toán này tại đây4
2. Ngoài ra ta cũng có thể xây dựng một thuật toán kết nối đến từ điển Việt
– Anh để xử lý. Quá trình sẽ được thực hiện như sau: Kết nối đến từ điển
và tìm các từ tiếng Anh tương ứng và sau đó sử dụng các thuật toán cho
tiếng Anh.
Sử dụng các phương pháp trên tất nhiên chúng ta phải có một bộ phân tích
cú pháp cho tiếng Việt, nghiên cứu sinh Lê Hồng Phương 5 đang phát triển dự án
vnLTAG6 cho tiếng Việt mục đích để xây dựng một văn phạm LTAG cho tiếng Việt.
Trước đó tác giả này đã xây dựng công cụ vnTokenizer để xử lý ngôn ngữ tiếng
Viêt có chức năng tact từ tiếng Việt tự động và phân loại chúng.
3
4
5 Doctorant, Equipe Langue et Dialogue, LORIA,INRIA Lorraine, 615 rue du Jardin
Botanique, lehong@loria.fr
6
35
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
3 Thiết kế
Trong phần này tôi trình bày về kiến trúc của hệ thống đối sánh lược đồ và
các bước thực hiện. Ý tưởng của hệ thống này là sử dụng đối sánh kết hợp
(compostion), sử dụng tổng hợp
3.1 Kiến trúc hệ thống
Kiến trúc của hệ thống đối sánh lược đồ của DocMatcher được mô tả trong
hình sau. Hệ thống bao gồm các module sau với sự hỗ trợ của giao diện đồ hoạ
trên nền Window:
• Xử lý thông tin đầu vào (input)
• Đối sánh với các thuật toán
• Tổng hợp kết quả
• Kết xuất thông tin ra
36
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
Hình 3-3: Kiến trúc hệ thống
3.2 Input
Đầu vào của hệ thống bao gồm các lược đồ cần đối sánh và các nguồn
thông tin hỗ trợ việc đối sánh.
3.2.1 Lược đồ
XSD là một trong những ngôn ngữ biểu diến lược đồ mạnh nhất và được
ứng dụng rộng rãi trong nhiều lĩnh vực. Vì vậy XSD được lấy làm ví dụ để minh
hoạ cho đầu vào của hệ thống đối sánh. Các tài liệu XML schema (XSD) được
phân tích và xử lý để chuyển đổi sang dạng đồ thị có hướng. Các ngôn ngữ biểu
diễn lược đồ khác như XML DTD hay SQL (ví dụ SQL-92) cũng có thể áp dụng
phương pháp mô hình hoá với XSD.
XSD có nhiều cách thiết kế mà chúng ta cần xem xét để phân tích các vấn
đề xung đột.
37
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
1. XSD Schema có thể được thiết kế theo kiểu phân tán hoặc nguyên khối,
thường thì các lược đồ được thiết kế theo cách truyền thống là tất cả các
thành phần được gộp vào chung một tài liệu. Tuy nhiên đối với các lược đồ
có kích thước lớn, đặc biệt là trong các ứng dụng Web Lược đồ được tách
thành nhiều tài liệu và các namespace khác nhau. Ví dụ các tài liệu XSD có
thể sử dụng các cú pháp include, redefine, import để tích hợp các tài liệu
với nhau.
2. Kiểu thiết kế Composition và Deviration: Một vài ngôn ngữ như XSD và
ngôn ngữ SQL mở rộng cho hướng đối tượng hỗ trợ việc định nghĩa kiểu rất
linh hoạt (user-defined types) cho các phần tử và thuộc tính. Các kiểu mới
có thể xây dựng dựa theo phương pháp composition hoặc derivation. Theo
phương pháp composition thì kiểu mới có thể xây dựng dựa trên các phần
tử và thuộc tính đã tồn tại. Theo phương pháp derivation thì các kiểu mới
được xây dựng bằng cách thừa kế các một kiểu cơ sở và các thuộc tính của
nó.
3. Phương pháp khai báo inline và khai báo chia sẻ: Khai báo inline là các
phần tử được khai báo kiểu ngay trong phạm vi khai báo của phần tử đó,
còn khai báo theo kiểu chia sẻ là định nghĩa ra các kiểu chung rồi các phần
tử có chung một kiểu sử dụng các kiểu chung đó.
Phân tích lược đồ đầu vào là một trong những bước quan trọng của bài
toán đối sánh.Các bước chuyển đổi từ lược đồ đầu vào thành đồ thị có hướng bao
gồm các bước sau:
1. Hợp nhất các thiết kế: Để dễ dàng điều khiển, các lược đồ được phân tích
và hợp nhất thành một lược đồ.
38
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
Hình 3-4: Hợp nhất các lược đồ phân tán
2. Hợp nhất các các kiểu thiết kế: Composition là phương pháp chung để xây
dựng kiểu, kiểu thừa kế (derivation) được chuyển thành kiểu composition
Hình 3-5: Hợp nhất các kiểu thiết kế lược đồ
3. Chuẩn hoá lược đồ bằng cách loại bỏ các nút biểu diễn kiểu (type).
Hình 3-6: Loại bỏ nút có kiểu đơn giản
4. Gộp các khai báo bằng cách chia sẻ các thành phần
39
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
Hình 3-7: Tái sử dụng các định nghĩa
Kết quả thu được là đồ thị liên thông có hướng biểu diễn lược đồ, với cách
biểu diễn này các lược đồ đầu vào được biểu diễn dưới dạng đơn giản nhất có thể.
3.2.2 WordNet
WordNet7 là cơ sở dữ liệu về từ vựng tiếng Anh. WordNet được thiết kế để
thực hiện kết nối cho các loại từ POS (Parts-of-Speech) gồm Danh từ, Động từ,
Tính từ và Trạng từ. Một khối nhỏ nhất trong WordNet được gọi là một synset để
biểu diễn ý nghĩa cho một từ cụ thể. Nó bao gồm một từ và giải nghĩa của từ đó
cộng với các từ đồng nghĩa. Ý nghĩa cụ thể của một từ theo POS được gọi là 1
sense. Mỗi sense của một từ nằm trong các synset khác nhau. Mỗi synset có chú
thích để định nghĩa khái niệm mà nó biểu diễn. Ví dụ từ night, nighttime, dark
cấu tạo một synset có chú thích như sau: “the time after sunset and before
sunrise while it is dark outside”. Synset kết nối đến các synset khác qua các quan
hệ ngữ nghĩa rõ. Một vài quan hệ như (hypernym, hynonym cho danh từ,
hypernym và troponym cho động từ) và cấu tạo thành cây is-a-kind-of
(holonymy) và is-a-part-of (meronymy cho danh từ).
Ví dụ tree is-a-kind-of plant, tree là hyponym của plant và plant là
hypernym của tree, tương tụ trunk is-a-part-of tree và tree là meronymy của
trunk.
7
40
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
Trong [8]8 có đề cập vấn đề sử dụng WordNet để xây dựng thuật toán tính
toán độ tương tự của hai câu. Hiện tại trong phiên bản này, do hạn chế về thời
gian nên WordNet chưa được tích hợp vào trong hệ thống để tính toán độ tương
tự. Thay vào đó là một bảng các cặp từ đồng nghĩa với độ chính xác 1.0. WordNet
sẽ được tích hợp vào hệ thống trong thời gian sắp tới.
3.2.3 Output
Đầu ra của bài toán đối sánh là tập các ánh xạ chỉ ra sự tương đương giữa
các phần tử của hai lược đồ. Ký hiệu ↔ để chỉ ra một ánh xạ giữa hai lược đồ, ví
dụ S1↔ S2 để chỉ ra một ánh xạ của hai lược đồ, hoặc s1↔ s2 để chỉ ra một ánh
xạ của hai phần tử.
Với một tập các ánh xạ như vậy, chúng ta cần các thao tác để hỗ trợ việc
sử dụng chúng trong các ứng dụng khác nhau.
Các hàm thao tác kết quả ánh xạ
Transpose(m: S1↔S2) {s2↔s1 | s1↔s2 ∈ m}
Domain(m: S1↔S2) {s1 ∈ S1 | Σs2 ∈S2 ∧ s1↔s2 ∈ m}
InvertDomain(m: S1↔S2) S1 \ Domain(m: S1↔S2)
RestrictDomain(m: S1↔S2, S) {s1↔s2 | s1↔s2 ∈m ∧ s1∈S}
MappingMerge(m1: S1↔S2, m2: S1↔S2) {s1↔s2 | s1↔s2 ∈m1 ∨ s1↔s2 ∈m2}
Diff(m1: S1↔S2, m2: S1↔S2) {s1↔s2 | s1↔s2 ∈ m1 ∧ s1↔s2 ∉m2}
Intersect(m1: S1↔S2, m2: S1↔S2) {s1↔s2 | s1↔s2 ∈m1 ∧ s1↔s2 ∈m2}
Bảng 2:
Chú thích:
• Transpose: Hoán đổi vị trí của phần tử nguồn và phần tử đích trong tất các
các ánh xạ đầu ra. Thao tác này không thể áp dụng cho các ánh xạ chưa
biểu thức, nó chỉ được dành riêng cho các giá trị tương tự.
8
41
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
• Domain và InvertDomain: Domain trả về tập các phần tử nguồn trong các
cặp ánh xạ. Ngược lại InvertDomain trả về tập các phần tử nguồn không
nằm trong tập các cạnh ánh xạ.
• RestrictDomain có tham số đầu vào là tập ánh xạ và tập các phần tử, kết
quả trả về tập các ánh xạ với các phần tử nguồn nằm trong tập các phần
tử đã cho
• MappingMerge: Tham số đầu vào là hai tập các ánh xạ và đầu ra là tập các
ánh xạ nằm trong cả hai tập ánh xạ đầu vào.
• Intersect: Tương tự MappingMerge.
• Diff: Tham số đầu vào là 2 tập ánh xạ và đầu ra là tập các ánh xạ chỉ nằm
mộ trong hai tập hợp đầu vào.
3.3 Mức ngôn ngữ (linguistic matching)
Pha đầu tiên của ứng dụng đối sánh lược đồ là dựa trên thuộc tính name và
description của các phần tử lược đồ cộng với sự hỗ trợ của từ điển đồng nghĩa, từ
điển viết tắt. Các bản ghi dữ liệu không được sử dụng để đối sánh ở bước này.
Kiến trúc của bước đầu tiên được minh hoạ trong hình sau:
Hình 3-8:Sơ đồ đối sánh mức ngôn ngữ (linguistic matching)
42
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
3.3.1 Các thuật toán đối sánh cơ bản
Các thuật toán cơ bản được áp dụng cho các phần tử đầu vào, đối với mỗi
thuật toán này ta xây dựng được một mảng các hệ số tương tự giữa các phần tử
đầu vào. Tiếp theo là ta xây dựng thuật toán kết hợp các kết quả đối sánh được
tính toán từ các thuật toán này.
Hệ thống áp dụng các thuật toán sau
1. EditDistance(ed): Giá trị tương tự tính toán theo hệ số ed được biến đổi
để đảm bảo giá trị các hệ số tương tự nằm trong khoảng [0,1]. Thuật toán
Levenshtein (hay được gọi là EditDistance) dùng để tính độ tương tự giữa
hai chuỗi s và t, khoảng Levenshtein là số lần cần thiết thực hiện các thao
tác xóa, thêm, thay đổi để chuyển từ một chuỗi s thành chuỗi t
• s là “document” , t là “document” thì LD(s,t)=0.
• s là “document” , t là “documents” thì LD(s,t)=1.
Giá trị của khoảng Levenshtein (LD) càng lớn thì sự khác nhau giữa hai
chuỗi càng lớn.
Ta xây dựng công thức tính độ tương tự của hai chuỗi dựa trên hệ số ed và
chuẩn hóa giá trị của nó trong khoảng [0,1], ta có công thức sau đây:
Công thức 4: Công thức EditDistance biến đổi
))(),(max(
),(1),(
tlenslen
tsldtssim −=
Trong đó: ld(s,t) là khoảng Levenshtein, max (len(s),len (t)) là chuỗi có độ
dài lớn nhất trong hai chuỗi s,t.
Như vậy công thức 1 tương đương với nếu sim(s,t) càng lớn thì sự giống
nhau càng lớn
43
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
Ví dụ:
s T sim(s,t)
Document Doc 0.37
Documents Document 0.89
Document Document 1
… … …
2. N-Gram:Chuỗi được so sánh theo tập n-gram của nó. Ví dụ chuỗi doc và
document là tương tự theo tập tri-gram, {doc} và
{doc,ocu,cum,ume,men,ent} chia sẻ phần tử doc.
Ví dụ:
s t sim(s,t)
… …
3. Synonym: Tổ chức một từ điển các từ đồng nghĩa hoặc có thể kết nối đến
WordNet để tra cứu các từ đồng nghĩa
Synonym
Customer Client
Customer Buyer
Tree Plant
provider supplier
… …
44
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
4. Abbreviation: Tổ chức một từ điển các từ viết tắt
Cust Customer
id identifier
phone telephone
doc document
…. …
3.3.2 Thuật toán đối sánh kết hợp
Mục đích của thuật toán này là kết hợp các kết quả tính toán của các thuật
toán cơ bản để xác định được các phần tử tương ứng giữa các phần tử của hai
lược đồ.
Sơ đồ thuật toán được mô tả sau đây
45
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
Hình 3-9: Sơ đồ thuật toán đối sánh kết hợp
Chú thích thuật toán
ExtractAttribute: Thực hiện việc phân tích các chuỗi đầu vào theo các quy tắc về
synonym, từ viết tắt, từ viết gọn, phân tích token…
matchers: Các thuật toán đối sánh cơ bản
agg: Phương pháp tổng hợp kết quả từ simCube
dir:Chiều so sánh của thuật toán, dựa trên số lượng phần tử của s1 và s2
sel: Phương pháp chọn lựa các giá trị đối sánh
combineMethod: Phương pháp tính toán kết hợp các kết quả
46
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
Phân tích các phần tử(Element)
Trong bước này ta phân tích phần tử thành các token bằng cách sử dụng
các phương pháp chuẩn hoá phần tử, danh mục các ký tự đặc biệt (stop word),
danh mục từ viết tắt (Abbreviation)…và một số tiêu chuẩn khác.
Kết quả của bước này thu được hai tập hợp tương ứng chứa các token của hai
phần tử.
Hình 3-10: Phân tích phần tử đầu vào
Tổng hợp các kết quả đối sánh (Aggregation)
Thực hiện các thuật toán đối sánh khác nhau sẽ thu được một ma trận 3
chiều (m,s1,s2) với m là thuật toán, s1,s2 tương ứng là các phần tử của hai lược
đồ. Các ô trong ma trận là giá trị các hệ số tương tự theo từng thuật toán. Từ ma
trận này tính ra được ma trận hai chiều hệ số tương tự của 2 phần tử (s1,s2) theo
các phương pháp sau đây.
s1
s2
Matcher
s1
s2
Sim_cube(m,s1,s2) Sim_array(s1,s2)
47
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
1. Max: Lấy hệ số tương tự lớn nhất của một thuật toán, sử dụng phương
pháp này sẽ cho kết quả tối ưu đặc biệt trong trường hợp giá trị tương tự
được chỉ định hoặc lấy trong các bảng hệ số.
Công thức 5: Lấy Max
),,(max),( 2121 ssmssMSim Mm∈=
2. Trọng số: Các thuật toán đối sánh được gán các trọng số ưu tiên khác nhau
wi, dựa trên các trọng số này sẽ tính được hệ số tương tự s1 và s2.
Công thức 6: Lấy theo trọng số
∑∑ ==
∈
1)s,s,(w )s,WSim(s
Mm
21m21 iwmsim
3. Trung bình: Trả về hệ số tương tự trung bình của các thuật toán đối với
(s1,s2)
Công thức 7: Lấy theo trung bình
∑
∈
=
Mm
msimA )s,s,(
M
1Sim 21
Xác định chiều đối sánh (Direction)
Xác định chiều đối sánh phụ thuộc và số lượng phần tử của s1 và s2, ký
hiệu là |s1|,|s2|. Có thể xảy ra 3 trường hợp sau
1. |s1|>|s2|: Đối sánh một lược đồ có số lượng phần tử lớn hơn với lược đồ
có số lượng phần tử nhỏ hơn, các phần tử s1 được so sánh với mỗi phần tử
s2
2. |s1|<|s2|:Đối sánh một lược đồ có số lượng phần tử nhỏ hơn với lược đồ
có số lượng phần tử lớn hơn, các phần tử s2 được so sánh với mỗi phần tử
s1
3. Cả hai chiều
Chọn lựa giá trị ứng cử (Select candidate)
1. Chon lựa theo ngưỡng: Xem xét các phần tử và giá trị tương tự không vượt
qua ngưỡng. (ví dụ 0.5)
48
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
2. MaxN: Chọn lựa theo số lượng phần tử có giá trị tương tự lớn nhất: Ví dụ
có 1 phần tử của S1 với hệ số có giá trị lớn nhất là 0,9, chọn giá trị này làm
giá trj ứng cử. Với n > 1 thì chúng ta có vài giá trị để tính toán
3. MaxDelta: Phần tử s1 vơi giá trị tương tự lớn nhất được chọn làm giá trị ứng
cử cộng với các phần tử
Hình 3-11: Thực hiện bước Direction và Selection
Tổng hợp kết quả
Bước tiếp theo là kết hợp các giá trị tương tự cho tập các token của một
phần tử. Để thực hiện việc này có thể sử dụng hai phương pháp Average và Dice
sau đây để tính. Hai phương pháp này đều sử dụng các giá trị ứng cử được lựa
chọn mc. Giả sử tất cả các giá trị ứng cử cho S1 và S2 đều được xác định, ta có 2
công thức sau:
1. Average: Giá trị tương tự trung bình được xác định bằng cách chia tổng các
giá trị tương tự của tất cả các giá trị ứng cử của 2 tập S1, S2 cho tổng các
phần tử của S1, S2.
49
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
Công thức 8: AverageSim
21
)1,2(22
))1,2(,2(
)2,1(11
))2,1(,1(
)2,1( SS
SsmcSs
Ssmcssim
SsmcSs
Ssmcssim
SSASim +
∑
∅≠∧∈
+∑
∅≠∧∈=
2. Dice: Phương pháp này dựa trên hệ số Dice[] và trả về tỷ lệ của số phần tử
có thể được đối sánh trên tổng số phần tử của S1, S2.
Công thức 9: DiceSim
{ } { }
21
)1,2(222)2,1(111)2,1( SS
SsmcSssSsmcSss
SSDSim +
∅≠∧∈+∅≠∧∈=
Đối với phương pháp Dice, ta nhận thấy các giá trị tương tự độc lập không
ảnh hưởng đến giá trị tương tự của toàn bộ tập hợp. Do vậy Dice sẽ tối ưu hơn và
cho giá trị tương tự lớn hơn so với phương pháp Average. Trong trường hợp tất cả
các giá trị ứng cử đều bằng 1.0 thì cả hai sẽ cho cùng một kết quả.
Hình 3-12: Tổng hợp kết quả
Ví dụ: Giả sử có hai phần tử cần đối sánh Document_Signer và
Dokument_User_Sign, sau khi phân tích thành các token ta có hai tập hợp sau
{Document,Signer} và {Dokument,User,Sign}, sau khi áp dụng các thuật toán
50
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
đối sánh cơ bản ta có ma trận 3 chiều các giá trị tương tự nhau. Áp dụng thuật
toán Max ta thu được mảng hai chiều các giá trị tương tự
Document Dokument NGram(3) 0.699999988
Document Dokument EditDistance 0.875
Document user NGram(3) 0
Document user EditDistance 0.25
Document sign NGram(3) 0
Document sign EditDistance 0.125
signer Dokument NGram(3) 0
signer Dokument EditDistance 0.125
signer user NGram(3) 0.285714298
signer user EditDistance 0.333333333
signer sign NGram(3) 0.571428597
signer sign EditDistance 0.666666667
CubeSim
Hình 3-13: SimCube theo phương pháp đối sánh kết hợp
Document Dokument EditDistance 0.875
Document user EditDistance 0.25
Document sign EditDistance 0.125
signer Dokument EditDistance 0.125
signer user EditDistance 0.333333333
signer sign EditDistance 0.666666667
SimMatrix
Hình 3-14: Kết quả sau khi thực hiện Aggregation
Document Dokument EditDistance 0.875
signer sign EditDistance 0.666666667
Dokument Document EditDistance 0.875
user signer EditDistance 0.333333333
sign signer EditDistance 0.666666667
Document_signer->Dokument_user_sign
Dokument_user_sign->Document_signer
Hình 3-15: Kết quả sau khi thực hiện Direction và Selection
51
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
Hình 3-16:Kết quả sau khi tổng hợp
3.4 Mức cấu trúc
Trong phần trước tôi đã trình bày thiết kế thuật toán đối sánh ở mức ngôn
ngữ đối với các phần tử của lược đồ. Kết quả đầu ra là một ma trận các hệ số đối
sánh tương ứng giữa các phần tử. Trong phần này tôi trình bày thuật toán đối
sánh mức cấu trúc (structure-base).
Thuật toán đối sánh mức cấu trúc dựa trên cấu trúc cây của lược đồ. Một
số khái niệm về cây trong thuật toán
• Node anh em: là các node có cùng cha
• Node lá: Là các node không có con
• Node trong: Không phải node lá
Đối sánh mức cấu trúc sẽ xem xét ngữ cảnh (context) của một node hiện
tại dựa trên các thông tin như các node lá, node cha, node con cháu…
Để tính độ tương tự cho hai node ta xây dựng các qui tắc sau.
1. Trường hợp các node lá: Hệ số tương tự được tính dựa trên các yếu tố sau:
hệ số tương tự mức ngôn ngữ, hệ số tương tự kiểu dữ liệu (data type), hệ
số tương tự của node cha và các anh chị em của nó. Ví dụ trong hình dưới
đây ta ta tính độ tương tự của hai node s3 và t4 dựa trên giá trị tương tự
của mức ngôn ngữ, kiểu dữ liệu (data type), các node anh em (s4,t5), các
node cha (s2,t2)
52
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
s1
s5s2
s4s3
t1
t3t2
t5t4
Sim(s3,t4)= Sim_context(lang,type,vicinity)
Hình 3-17: Hệ số tương tự của 2 node lá
2. Trường hợp các node giữa: Hệ số tương tự được tính dựa trên các yếu tố
sau: hệ số tương tự mức ngôn ngữ, hệ số tương tự kiểu dữ liệu (data
type), hệ số tương tự của cây con có gốc tại hai node đó tương tự nhau.
s1
s5s2
s4s3
t1
t3t2
t5t4
Sim(s1,t1)= Sim_context(lang,type,subtree)
Hình 3-18: Hệ số tương tự của 2 node trong
53
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
Thuật toán đối sánh lược đồ dựa trên cấu trúc được mô tả dưới đây
TreeMatch(Source S, Target T)
For s ∈ S, t ∈ T (s,t: leaves)
Set ssim(s,t) = datatype_match(s,t)
S’=post_order(S), T’=post_order(T)
For each s in S’
For each t in T’
ssim(s,t)=struct_sim(s,t)
wsim(s,t)=wstruct.ssim(s,t)+(1-wstruct)lsim(s,t)
if(wsim(s,t)>thhigh)
increase_struct_sim(leaves(s),leaves(t),cinc)
if(wsim(s,t)<thlow)
decrease_struct_sim(leaves(s),leaves(t),cinc)
Giải thích thuật toán:
1. Đầu tiên ta khởi tạo hệ số đối sánh theo cấu trúc ssim theo kiểu dữ liệu
của phần tử được so sánh. Thủ tục datatype_match(s,t) được tham chiếu
vào một bảng định nghĩa sẵn các hệ số đối sánh theo kiểu dữ liệu. Hệ số
dsim(s,t) này nằm trong khoảng [0,1], nhằm mục đích tăng giảm các hệ
số sau này, dsim được chuẩn hóa về khoảng [0,0.5] (dsim=dsim/2). Bảng
đối sánh được định nghĩa tương tự bảng sau.
Type(s) Type(t) datatype_match(s,t)
string string 1.0
string date 0.2
decimal float 0.8
float float 1.0
float integer 0.9
… … …
2. Các phần tử của hai cây được duyệt theo thứ tự sau.
54
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
3. Trường hợp các phần tử là lá (leaf): Bước tiếp theo tính giá trị đối sánh cho
hai phần tử s và t, giá trị ssim(s,t) chính là giá trị được tính trong vòng lặp
trước với luật đối sánh trên kiểu dữ liệu của phần tử
(datatype_match(s,t)). Trong đó wstruct là hệ số chỉ ra độ ưu tiên của đối
sánh cấu trúc so với đối sánh mức ngôn ngữ. wstruct thường được chọn bằng
0.5
Công thức 10: Wsim cho các node lá
wsim(s,t)=wstruct.ssim(s,t)+(1-wstruct)lsim(s,t)
Ví dụ: Trong ví dụ tính lsim của phần tử document_signer và
document_user_sign cho giá trị 0.68. Hệ sô sim(s,t) với tiêu chí là kiểu dữ
liệu có giá trị 0.5(giá trị max)
Ta có wsim (s,t)=0.5(0.5)+0.5.0.68=0.59
4. Trường hợp các phần tử không phải là lá (leaf):Khi một trong các phần tử
không phải là lá (leaf), ssim được tính dựa trên số lượng của lá trong cây
con có gốc tại các phần tử đang được so sánh.Một node lá trong một lược
đồ nếu có một liên kết mạnh (strong link) tới một node lá trong một lược
đồ khác nếu trọng số tương tự vượt qua ngưỡng chấp nhận được (thaccept).
Trong công thức dưới đây trả về tập hợp các node lá trong cây con có gốc
là s và có ít nhất một liên kết mạnh với node lá của cây có gốc là t.
Công thức 11: Liên kết mạnh
{ }acceptthyxwsimtleavesysleavesxxtssl >∈∃∧∈= ),(),()(),(
Công thức tính hệ số tương tự cuối cùng là:
Công thức 12: ssim trong trường hợp là các node trong
)()(
),(),(
),(
tleavessleaves
stsltssl
tsssim +=
Υ
Trong đó leaves(s): là số node lá của cây có gốc tại s
5. Nếu hai phần tử được so sánh là có mức giống nhau cao, ví dụ hệ số tương
tự vượt quá ngưỡng thhigh thì tăng ssim của từng cặp của lá trong hai cây
con có gốc tương ứng bởi hai phần tử một giá trị cinc (Tăng ssim nhưng
không vượt quá 1.0). Ngược lại nếu hệ số tương tự nhỏ hơn thlow thì ta
55
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
giảm ssim của các node lá đi một giá trị cdec. Ví dụ trong hình 8, Org_Send
được ánh xạ với Sender có hệ số giống nhau cao nên các node con của hai
node đó được tăng thêm độ giống nhau hơn so với cặp name, address
khác, tương tự như vậy nếu hệ số ssim nhỏ hơn ngưỡng thlow ta sẽ giảm hệ
số ssim của các node lá
Document
Signer Org_Send
Firstname Lastname
Org_name Org_address
Org_Receive
Org_name Org_address
Docs
Signer Sender
Name
OrgName OrgAddress
DeliverTo
name address
Organization
ssim++
ssim--
Hình 3-19: Sự phụ thuộc của hệ số tương tự vào ngữ cảnh
Trong thuật toán đối sánh dựa trên cấu trúc ở trên ta đã xem xét các yếu tố liên
quan đến ngữ cảnh của từng phần tử trong lược đồ. Hai phần tử là tương tự nếu
các lá của chúng là tương tự. Hệ số tương tự của các node lá được tăng hay giảm
lại phụ thuộc vào node tổ tiên của chúng. Duyệt cây theo thứ tự sau bảo đảm
rằng trước khi hai phần tử s1,s2 được so sánh thì các node lá của chúng đã được
so sánh.
3.5 Chọn lựa ánh xạ
Sau khi thực hiện hai thuật toán đối sánh mức ngôn ngữ và đối sánh mức
cấu trúc ta có một tập các ánh xạ giữa các phần tử của hai lược đồ đầu vào. Đầu
tiên ta xét trường hợp là các node lá, nếu với mỗi phần tử t trong lược đồ nguồn
56
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
và s trong lược đồ đích nếu ssim lớn hơn một giá trị thaccept (giá trị ngưỡng chấp
nhận được) thì chọn ánh xạ này. Đối với trường hợp không là node lá, ta sẽ duyệt
theo thứ tự sau hai lược đồ một lần nữa để tính toán lại hệ số tương tự của các
node không phải là lá vì quá trình cập nhật hệ số tương tự của các node lá sẽ ảnh
hưởng đến hệ số tương tự của các node không phải là lá.
4 Cài đặt và kết quả
4.1 Cài đặt
Hệ thống Demo được xây dựng bằng công cụ Visual Studio .Net 2003, cung cấp
giao diện đồ hoạ với các chuẩn sau
• Ngôn ngữ cài đặt C#
• XML và XML Schema
• Các thư viện opensource
o WordNet.Net: Từ điển từ vựng tiếng Anh
o QuickGraph9: Thư viện hỗ việc xây dựng đồ thị trên ngôn ngữ C#
• Môi trường cài đặt: Window 2000 , Window XP, Window 2003 với Net
Framework
Cấu trúc chương trình
9
57
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
Hình 3-20:Cấu trúc VNMatch
• 3rdParty: Các thư viện hỗ trợ lập trình
• Linguistic: Các thuật toán xử lý ngôn ngữ: EditDistance, NGram …
• MatchLib: Phần core của VNMatch, bao gồm đối sánh ngôn ngữ và đối sánh
cấu trúc
• Schemas: Phần phân tích xử lý lược đồ đầu vào.
• Sources: Chứa các lược đồ mẫu
• Utils:Một số hàm hỗ trợ
• ui:Phần giao diện chương trình
Hình 3-21: MatchLib, phần core của VNMatch
Lớp HybridMatcher chứa các hàm thực hiện việc đối sánh mức ngôn ngữ
giữa các phần tử của hai lược đồ.
58
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
Hình 3-22: Lớp HybridMatcher
Thông tin hỗ trợ
Thông tin hỗ trợ của VNMatch bao gồm các danh mục sau
• Bảng Synonym (thesauri.xml): chứa danh mục các từ đồng nghĩa
• Bảng Abbreviation (abbreviation.xml): Chứa các từ được viết gọn
59
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
• Bảng DataType (datatype.xml): Chứa các ánh xạ giữa các kiểu dữ liệu
60
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
4.2 Kết quả thử ngiệm
Thử nghiệm trên 2 lược đồ đầu vào, hai lược đồ này biểu diễn mô hình các
đối tượng trong một phiếu thanh toán đơn hàng.
Schema1
<xsd:schema xmlns:xsd=""
elementFormDefault="qualified">
61
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
62
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
63
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
64
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
Schema2
<xsd:schema xmlns:xsd=""
elementFormDefault="qualified">
65
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
66
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
67
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
Kết quả
68
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
- PurchaseOrder.InvoiceTo.Address.country
PurchaseOrder.InvoiceTo.Address.country: 0.9958
- PurchaseOrder.InvoiceTo.Address.postalCode
PurchaseOrder.InvoiceTo.Address.postalCode: 0.9958
- PurchaseOrder.InvoiceTo.Address.street1
PurchaseOrder.InvoiceTo.Address.street: 0.9958
- PurchaseOrder.InvoiceTo.Address.city
PurchaseOrder.InvoiceTo.Address.city: 0.9958
- PurchaseOrder.InvoiceTo.Address.stateProvince
PurchaseOrder.InvoiceTo.Address.state: 0.97213334
- PurchaseOrder.InvoiceTo.Address PurchaseOrder.InvoiceTo.Address:
0.85524625
- PurchaseOrder.InvoiceTo.Contact.contactName
PurchaseOrder.ContactPerson.firstName: 0.61975986
- PurchaseOrder.InvoiceTo.Contact.contactName
PurchaseOrder.ContactPerson.lastName: 0.621613
- PurchaseOrder.InvoiceTo.Contact.companyName
PurchaseOrder.InvoiceTo.Organization.name: 0.61861247
- PurchaseOrder.InvoiceTo.Contact.e-mail
PurchaseOrder.ContactPerson.email: 0.5943921
- PurchaseOrder.InvoiceTo.Contact.telephone
PurchaseOrder.ContactPerson.tel: 0.7819118
- PurchaseOrder.InvoiceTo.Contact PurchaseOrder.ContactPerson: 0.64217
- PurchaseOrder.InvoiceTo PurchaseOrder.InvoiceTo: 0.77725554
- PurchaseOrder.Items.Item.partDescription
PurchaseOrder.Line.productName: 0.6937629
- PurchaseOrder.Items.Item.unitOfMeasure
PurchaseOrder.Line.unitOfMeasureRef: 0.8225684
- PurchaseOrder.Items.Item.quantity PurchaseOrder.Line.quantity:
0.85372746
69
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
- PurchaseOrder.Items.Item.unitPrice PurchaseOrder.Line.unitPrice:
0.8566578
- PurchaseOrder.Items.Item.itemNumber PurchaseOrder.Line.lineNo:
0.8529762
- PurchaseOrder.Items.Item.partNumber PurchaseOrder.Line.productRef:
0.86023074
- PurchaseOrder.Items.Item PurchaseOrder.Line: 0.66273284
- PurchaseOrder.Header.yourAccountCode PurchaseOrder.currencyCode:
0.5750351
- PurchaseOrder.Header.orderNum PurchaseOrder.customerOrderRef:
0.73732954
- PurchaseOrder.Header.Contact.contactName
PurchaseOrder.ContactPerson.firstName: 0.62261695
- PurchaseOrder.Header.Contact.contactName
PurchaseOrder.ContactPerson.lastName: 0.62415266
- PurchaseOrder.Header.Contact.e-mail
PurchaseOrder.ContactPerson.email: 0.59765023
- PurchaseOrder.Header.Contact.telephone
PurchaseOrder.ContactPerson.tel: 0.78516996
- PurchaseOrder.Header.Contact PurchaseOrder.ContactPerson: 0.64673144
- PurchaseOrder.Header.orderDate PurchaseOrder.orderDate: 0.79244316
- PurchaseOrder.DeliverTo.Address.country
PurchaseOrder.DeliverTo.Address.country: 0.9958
- PurchaseOrder.DeliverTo.Address.postalCode
PurchaseOrder.DeliverTo.Address.postalCode: 0.9958
- PurchaseOrder.DeliverTo.Address.street1
PurchaseOrder.DeliverTo.Address.street: 0.9958
- PurchaseOrder.DeliverTo.Address.city
PurchaseOrder.DeliverTo.Address.city: 0.9958
70
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
- PurchaseOrder.DeliverTo.Address.stateProvince
PurchaseOrder.DeliverTo.Address.state: 0.97213334
- PurchaseOrder.DeliverTo.Address PurchaseOrder.DeliverTo.Address:
0.85524625
- PurchaseOrder.DeliverTo.Contact.contactName
PurchaseOrder.ContactPerson.firstName: 0.619998
- PurchaseOrder.DeliverTo.Contact.contactName
PurchaseOrder.ContactPerson.lastName: 0.6215336
- PurchaseOrder.DeliverTo.Contact.companyName
PurchaseOrder.DeliverTo.Organization.name: 0.61861247
- PurchaseOrder.DeliverTo.Contact.e-mail
PurchaseOrder.ContactPerson.email: 0.59503114
- PurchaseOrder.DeliverTo.Contact.telephone
PurchaseOrder.ContactPerson.tel: 0.78255093
- PurchaseOrder.DeliverTo.Contact PurchaseOrder.ContactPerson:
0.64306474
- PurchaseOrder.DeliverTo PurchaseOrder.DeliverTo: 0.77725554
- PurchaseOrder PurchaseOrder: 0.8594128
71
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
5 Kết luận và hướng phát triển
Phần này sẽ tóm tắt lại các vấn đề đã được nghiên cứu và giải quyết trong
luận án, và tiếp theo sẽ là các xu hướng sẽ được nghiên cứu trong tương lai.
5.1 Kết luận
Đối sánh lược đồ là một module quan trọng để giải quyết vấn đề tương tác
giữa các ứng dụng và tích hợp dữ liệu trong nhiều lĩnh vực. Để giảm thiểu các
thao tác thủ công nhiều nhất có thể, các phương pháp tiếp cận bán tự động
(semi-automatic) cần hỗ trợ một cách hiệu quả người dùng trong bài toán đối
sánh lược đồ. Luận văn này nghiên cứu về thực trạng của bài toán đối sánh lược
đồ, thiết kế và thi công một ứng dụng đối sánh. Luận văn bao gồm các phần
chính sau:
Tổng quan về bài toán đối sánh lược đồ và các phương pháp tiếp cận
Đầu tiên phân loại các dạng bài toán đối sánh để có một cái nhìn tổng quan
về các phương pháp đã được đề cập. Dựa vào sự phân loại các bài toán, các
phương pháp được sử dụng, đối sánh lược đồ được chia thành các phương pháp
cơ bản sau: schema-based, instance-based, element-based, structure-based,
language-based, constraint-based. Tiếp theo mô tả các kỹ thuật được sử dụng
trong từng phương pháp đối sánh. Ngoài ra luận văn còn đề cập đến các phương
pháp đánh giá hiệu quả của các thuật toán. Và cuối cùng là một số đề xuất
phương pháp giải quyết cho các lược đồ được xây dựng bằng tiếng Việt.
Thiết kế hệ thống đối sánh lược đồ VNMatch
VNMatch được xây dựng trên cách tiếp cận của COMA++ và Cupid [3].
VNMatch xử lý dữ liệu đầu vào là các lược đồ được thiết kế bằng ngôn ngữ
XMLSchema1. Phần đối sánh dựa trên ngôn ngữ (language-based) của VNMatch
dựa trên mô hình của COMA++, tuy nhiên VNMatch được thiết kế một cách mềm
1
72
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
dẻo để dễ dàng bổ xung thêm các matcher (thuật toán đối sánh ) để nâng cao độ
chính xác. Phần đối sánh mức cấu trúc (Structure-based) được thiết kế dựa trên
mô hình của Cupid [3], đối sánh cấu trúc được thực hiện trên ngữ cảnh của node
được so sánh, trong VNMatch ngữ cảnh được xét cho một node là các node lá của
nó.
5.2 Hướng phát triển
Mặc dù đã cố gắng hoàn thành luận văn về đối sánh lược đồ nhưng cũng
còn rất nhiều vấn đề cầnphải làm để nâng cao được chất lượng của kết quả đối
sánh. Mục tiêu của tôi trong thời gian sắp tới là tiếp tục hoàn thiện VNMatch theo
hai tiêu chí sau đây.
Hoàn thiện VNMatch
• Xử lý được các lược đồ dữ liệu đầu vào như chuẩn SQL, OWL, XDR …
• Làm mịn các thuật toán đối sánh dựa trên ngôn ngữ và cấu trúc, đặc
biệt là kết hợp thêm các phương pháp đối sánh có cấu trúc để nâng
cao chất lượng kết quả.
• Xây dựng một thuật toán đối sánh đơn giản dựa trên ngôn ngữ cho
tiếng Việt.
• Tìm một bài toán tích hợp dữ liệu hoặc chuyển đổi dữ liệu cụ thể để
áp dụng VNMatch.
Xây dựng VNMatch Framework
Xây dựng VNMatch thành một framework để thực hiện các bài toán đối
sánh lược đồ. Việc phát triển một framework cho bài toán đối sánh này cũng được
đánh giá rất quan trọng. Dựa trên framework, các nhà nghiên cứu sau này có thể
tận dụng được các thuật toán có sẵn cũng như dễ dàng cài đặt một hệ thống đối
sánh mà không phải mất nhiều thời gian. VNMatch Framework có các tính năng
sau:
• Về mặt kỹ thuật VNMatch Framework sẽ cung cấp khả năng tùy biến
(customization) đối với các thuật toán đối sánh (matcher). Tùy biến
quá trình tổng hợp kết quả của các thuật toán.
73
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
• Người sử dụng thực thi một thuật toán mới (matcher) có thể dễ dàng
thêm vào hệ thống và kiểm tra được chất lượng của thuật toán.
• Hỗ trợ những người nghiên cứu sau này có một công cụ để kiểm tra
các kết quả nghiên cứu một cách nhanh nhất
• Có thể tái sử dụng các kết quả nghiên cứu trước. Người dùng sẽ
dành thời gian nghiên cứu phát triển các thuật toán đối sánh mà
phải quan tâm nhiều đến phần cài đặt và tổng hợp.
Hình 3-23: VNMatch Framework (đề xuất)
VNMatch Framework bao gồm các thành phần chính sau
74
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
1. Biểu diễn lược đồ: Module này xử lý các loại lược đồ đầu vào cơ bản như
SQL, XML Schema. Cung cấp một mô hình biểu diễn dưới dạng đồ thị cho
tất cả các loại lược đồ.
2. Các Matcher: Các Matcher sẽ được thêm mới, thay đổi, hoặc loại bỏ trong
hệ thống.
3. Matcher Combination Controller: Đây là phần nhân của hệ thống, sử dụng
các đặc tả được định nghĩa trong Matcher Configuration và Combination
configuration để xử lý.
4. Biểu diễn ánh xạ đầu ra
VNMatch framework rất cần được sự hỗ trợ của các thầy, các cô và các bạn sinh
viên để có thể trở thành một công cụ đắc lực phục vụ trước hết cho cộng đồng
những người nghiên cứu về lĩnh vực này.
75
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
Tài liệu tham khảo
Sách, bài báo, luận văn
[1]. AnHai Doan,Alon Y. Halevy Sem. Sematic Integration in the database
community: A Brief surve, 2005
[2]. Natalya F.Noy: Semantic Integration: A survey of ontology-based
approaches, 2005
[3]. Jayant Madhavan, Philip A.Bernstein, Erhard Rahm. Generic schema
matching with Cupid, 2001
[4]. Karthik Jagannathan: An approach to schema mapping generation for data
warehousing, 2003
[5]. Adia Boukottaya, Christine Vanoirbeek 2005. Schema Matching for
Transforming Structured Documents,2005
[6]. Rahm, E., P.A. Bernstein: A Survey of Approaches to Automatic Schema
Matchin,2001
[7]. Do Hong Hai Ph.D. Thesis:Schema matching anf mapping-based Data
integration, 2005
[8]. Troy Simpson, Thanh Dao: WordNet-based semantic similarity
measurement
[9]. Information Retrieval 2nd edition, C. J. Van Rijsbergen.
[10]. Melnik, S., H. Garcia-Molina, E. Rahm: Similarity Flooding: A
Versatile Graph Matching Algorithm and its Application to Schema Matching,
2002
Website
[11]. World Wide Web Consortium
[12]. OntologyMatching
[13]. The MOMIS Project
76
Luận văn Th.s: Tìm hiểu về đối sánh lược đồ và xây dựng ứng dụng VNMatch
Ngô Văn Quân, lớp cao học CNTT 2004
[14].
[15]. COMA++ project
[16]. Similarity Flooding
project
[17]. Data, Information, and Process
Integration with Semantic Web Services
--- Hết---
Các file đính kèm theo tài liệu này:
- 000000208321R.pdf