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)