C# – Thuật toán tìm kiếm chuỗi (string) gần đúng

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ả

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.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é.

(st)

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s