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