1. /conferences/conference/paper/authorname
2. /conferences/conference/submission/author/name
3. /universities/university/department/name
จากตัวอย่าง แสดงให้เห็นว่า เอกสาร 1 และ 2 น่าจะมีความเหมือนกัน โดยที่เอกสาร 3 ไม่น่ามีความเกี่ยวข้องกัน หรือเกี่ยวข้องกันน้อยมาก
XML Path ใช้ใน data integration, data querying, and data cleaning ซึ่งเป็นหัวข้อสำคัญ
Path Similarity ควรเพียงพอสำหรับในการอธิบายความหมายเช่น
- hire/date กับ birth/date ซึ่งคนละความหมายกัน
- คำที่มีความหมายเหมือนกัน หรือพิมพ์ผิด
การเปรียบเทียบโครงสร้างของ XML มีหลายการค้นคว้า โดยแบ่งออกเป็น similarity based on the tree edit distance และ combining the similarity values measured among their child elements. ทั้งสองวิธีเปรียบเทียบ element ไม่ใช่ path
COMA เป็น framework ที่ทำ schema matchers ซึ่งเรียกว่า NamePath (Path Similarity function) NamePath แปลง element ทุกตัวไปในรูป string และนำ string ไปเทียบหาความเหมือน
PathSim คือ similarity algorithm โดยแปลง XML part เป็น list ของ element names และใช้ edit distance มาเปรียบเทียบ list โดยมองว่า แต่ละ path คือ string แต่ไม่ได้เปรียบเทียบที่ละตัวตามลำดับอักษร แต่มองว่าแต่ละ path แสดงถึง list ของ element
PathSim คำนวนความคล้ายกันของสอง path โดยใช้ edit distance ระหว่าง list ของ element
PathSim ใช้ Matrix ในการคำนวนหาค่าความคล้ายกันของ 2 path โดยมีขั้นตอนดังนี้
1. สร้าง Matrix ที่มีแถว I + 1 และมีคอลัมภ์ j + 1
2. เติมค่าในแถวแรกและคอลัมภ์แรกด้วย
a. แถวแรก M[0,q] = q สำหรับ 0 <= q <= j
b. คอลัมภ์แรก M[p,0] = p สำหรับ 1 <= p <= i
3. เติมค่าที่เหลือโดยเลือกค่าที่น้อยที่สุดจาก
a. ค่าของ cell ข้างบน + 1
b. ค่าของ cell ทางซ้าย + 1
c. ค่าของ cell ทางซ้ายบน + ค่าความไม่เหมือนกันของ A[p] กับ B[q]
(M[p-1,q-1] + (1 – Sim(A[p],B[q]))
ตัวอย่าง
จาก 2 path A=”Author/Names” และ B=”Author/Name/First” สร้าง Matrix 2*3 และเติมค่าในแถวและคอลัมภ์แรกดังรูปที่ 1 หลังจากนั้นเติมค่าในช่องที่เหลือ
ค่า M[2,1] (Names,Author) คำนวนโดยใช้
ทางเลือกที่ 1 คือ Cell ข้างบน + 1 ได้ค่า 1
ทางเลือกที่ 2 คือ Cell ซ้าย + 1 ได้ 3
ทางเลือกที่ 3 คือ Cell บนซ้าย + ความไม่เหมือนกัน ได้ 1 + (1+1) = 3
เพราะฉะนั้นเลือกทางเลือกที่ 1 ซึ่งหมายความได้ว่า มีการเพิ่มค่า element ใน path A หรือเอาค่า element ออกจาก path B
ค่า M[2,2] ทางเลือกที่ 1 และ 2 ได้ค่า 2 ทั้งคู่
ทางเลือกที่ 3 เอาค่า 0 + ค่าความไม่เหมือน (1 – ค่าความเหมือน) ในที่นี่คือ 1 – 0.8 ได้ 0.2
เพราะฉะนั้น M[2,2] = 0.2
ค่าความเหมือนของ Name และ Names คือ 0.8 เพราะฉะนั้นค่าความไม่เหมือน คือ 0.2
ค่า M[2,3] คำนวนโดยใช้ทางเลือกที่ 2 หมายความได้ว่า มีการเพิ่ม element ใน path B หรือเอา element ออกจาก path A
การคำนวนค่าความเหมือนของ สอง path ใช้สูตร
PathSim(A,B) = 1 – M[I,j]/Max(I,j)
จากตัวอย่างค่า edit distance สูงสุดคือ 1.2 ใน cell M[2,3] ดังนั้นค่าความเหมือนคือ
PathSim (A,B) = 1 – 1.2/3 = 0.6
Ref : A.R. Vinson, C.A. Heuser, A.S. da Silva, E.S. De Moura, “An Approach to XML Path Matching”, 9th Annual ACM International Workshop on Web Information and Data Management, Lisbon, Portugal, 2007, pp. 17-24.
