Thứ Hai, ngày 08 tháng 3 năm 2010

// // Leave a Comment

Thuật toán tìm kiếm chuỗi

Thuật toán dùng cho từ điển thế thôi , ngoài ra còn có thể dùng để làm kiểm tra chính tả

Giới thiệu

Tôi xin giới thiệu với các bạn tư tưởng cả thuật toán như sau:

+Đầu tiên kiểm tra độ dài string so sánh :ít hay hơn 30% thì loại

+Tiếp là so sánh từng ký tự của 2 string nếu không bằng nhau thì lỗi cộng thêm 1, so sánh các từ lân cận tiếp theo của cả 2 string ,
Trong khoảng sai số nếu có , thì chỉnh lại vị trí i,j là chỉ số của 2 string đó, cái này sẽ kiểm tra các lỗi thừa hay thiếu từ , đọc ký tự kế tiếp .

+Cuối cùng , khi 1 trong 2 string đã đi hết
thì còn mẩu đuôi ta làm : loi += s.Length - i + s1.Length - j;
tức là nếu 1 string còn thừa thì cho mẩu đó là lỗi cộng vào
nếu số lỗi <=30% thì là đạt , không thì không đạt , đơn giản vậy thôi


Lớp xử lý

Từ tư tưởng được trình bày ở trên, tôi xây dựng lớp xử lý.

class
ApproximatString
{
string
s;
int
i, j, k, loi, saiSo;
public ApproximatString(string
nhap)
{
s =
nhap;
saiSo = (int)Math.Round(s.Length * 0.3
);
}

public bool SoSanh(string s1)
{
if (s1 == "database"
)
{
i =
i;
}
if (s1.Length < (s.Length - saiSo) || s1.Length > (s.Length +
saiSo))
return false
;
i = j = loi = 0
;
while (i < s.Length && j < s1.
Length)
{
if (s[i] !=
s1[j])
{
loi++
;
for (k = 1; k <= saiSo; k++
)
{
if ((i + k < s.Length) && s[i + k] ==
s1[j])
{
i +=
k;
//loi += k - 1;
break
;
}
else if ((j + k < s1.Length) && s[i] == s1[j +
k])
{
j +=
k;
//loi += k - 1;
break
;
}
}
}
i++
;
j++
;
}
loi += s.Length - i + s1.Length -
j;
if (loi <=
saiSo)
return true
;
else return false
;
}
}

Kết luận

Nếu ai muốn biết nó hoạt động thế nào thì down từ điển super power dict phần tìm kiếm nâng cao về dùng thử nhé.

itgatevn.com.vn

0 comments: