• Vui lòng đọc nội qui diễn đàn để tránh bị xóa bài viết
  • Tìm kiếm trước khi đặt câu hỏi

Thuật toán tìm kiếm string gần đúng

Đây là nơi để các bạn trao đổi về cấu trúc dữ liệu và giải thuật

Điều hành viên: Điều hành

tienlbhoc
Thành viên tâm huyết
Thành viên tâm huyết
Bài viết: 415
Ngày tham gia: T.Bảy 14/07/2007 10:06 pm
Đến từ: Hà Nội
Been thanked: 1 time

Thuật toán tìm kiếm string gần đúng

Gửi bàigửi bởi tienlbhoc » T.Năm 10/04/2008 2:39 pm

mới chế cái code tìm kiếm gần đúng , nhờ mọi người cho ý kiến cái :
Tư tưởng 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ì 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ừ , nếu có thì số lỗi là số ký tự phải chỉnh lại vị trí i,j .còn nếu không thì cho lỗi là 1 , đọ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

Code rất ngắn (để tốc độ cho nhanh mà):

Mã: Chọn hết

  1. class ApproximatString
  2. {
  3.     string s;
  4.     int i, j, k, loi, saiSo;
  5.     public ApproximatString(string nhap)
  6.     {
  7.         s = nhap;
  8.         saiSo = (int)Math.Round(s.Length * 0.3);
  9.     }
  10.     public bool SoSanh(string s1)
  11.     {
  12.         if (s1.Length < (s.Length - saiSo) || s1.Length > (s.Length + saiSo))
  13.             return false;
  14.         i = j = loi = 0;
  15.         while (i < s.Length && j < s1.Length)
  16.         {
  17.             if (s[i] != s1[j])
  18.             {
  19.                 loi++;
  20.                 for (k = 1; k <= saiSo; k++)
  21.                 {
  22.                     if ((i + k < s.Length) && s[i + k] == s1[j])
  23.                     {
  24.                         i += k;
  25.                         break;
  26.                     }
  27.                     else if ((j + k < s1.Length) && s[i] == s1[j + k])
  28.                     {
  29.                         j += k;
  30.                         break;
  31.                     }
  32.                 }
  33.             }
  34.             i++;
  35.             j++;
  36.         }
  37.         loi += s.Length - i + s1.Length - j;
  38.         if (loi <= saiSo)
  39.             return true;
  40.         else return false;
  41.     }
  42. }

Còn đây là kết quả:
Hình ảnh
Sửa lần cuối bởi tienlbhoc vào ngày T.Năm 18/09/2008 2:17 pm với 1 lần sửa.


Diễn đàn và blog phần mềm tự làm :
http://my.opera.com/DienDanTienlbhoc/forums/
http://my.opera.com/tienlbhoc/blog/

Hình đại diện của người dùng
ngaymaikhongtan
Thành viên chính thức
Thành viên chính thức
Bài viết: 38
Ngày tham gia: T.Bảy 29/03/2008 12:05 pm
Đến từ: Cà Mau
Liên hệ:

Re: Thuật toán tìm kiếm string gần đúng

Gửi bàigửi bởi ngaymaikhongtan » T.Bảy 12/04/2008 7:23 am

Ý tưởng cũng khá hay, nhưng minh vẩn không hĩu chổ này, bạn giải thích cho mình rỏ nhe, tai sao bạn chọn kiểm tra độ dài string so sánh :ít hay hơn 30% thì loại, tại sao bạn lại chọn mức la 30% vậy!
welcome to
http://gocnhinviet.com

tienlbhoc
Thành viên tâm huyết
Thành viên tâm huyết
Bài viết: 415
Ngày tham gia: T.Bảy 14/07/2007 10:06 pm
Đến từ: Hà Nội
Been thanked: 1 time

Re: Thuật toán tìm kiếm string gần đúng

Gửi bàigửi bởi tienlbhoc » T.Bảy 12/04/2008 8:03 am

thuật toán trên mình sửa rồi , cái đoạn tìm lân cận chỉ cho mặc định lỗi ++ thôi (vì thế kết quả sẽ rộng hơn).
Còn vì sao là 30% vì 20% mình thử thấy hơi ít 40% thấy hơi nhiều , con số này tuỳ theo thực nghiệm mà chỉnh thôi .
Còn vì sao mà độ dài lớn hơn hoặc nhỏ hơn 30% vì ví dụ a so sánh với application , thì dài thế này có cần phải so sánh nữa không hả , làm chậm chương trình.

Mã: Chọn hết

  1. class ApproximatString
  2. {
  3.     string s;
  4.     int i, j, k, loi, saiSo;
  5.     public ApproximatString(string nhap)
  6.     {
  7.         s = nhap;
  8.         saiSo = (int)Math.Round(s.Length * 0.3);
  9.     }
  10.     public bool SoSanh(string s1)
  11.     {
  12.         if (s1.Length < (s.Length - saiSo) || s1.Length > (s.Length + saiSo))
  13.             return false;
  14.         i = j = loi = 0;
  15.         while (i < s.Length && j < s1.Length)
  16.         {
  17.             if (s[i] != s1[j])
  18.             {
  19.                 loi++;
  20.                 for (k = 1; k <= saiSo; k++)
  21.                 {
  22.                     if ((i + k < s.Length) && s[i + k] == s1[j])
  23.                     {
  24.                         i += k;
  25.                         break;
  26.                     }
  27.                     else if ((j + k < s1.Length) && s[i] == s1[j + k])
  28.                     {
  29.                         j += k;
  30.                         break;
  31.                     }
  32.                 }
  33.             }
  34.             i++;
  35.             j++;
  36.         }
  37.         loi += s.Length - i + s1.Length - j;
  38.         if (loi <= saiSo)
  39.             return true;
  40.         else return false;
  41.     }
  42. }
Diễn đàn và blog phần mềm tự làm :
http://my.opera.com/DienDanTienlbhoc/forums/
http://my.opera.com/tienlbhoc/blog/

giongto35
Thành viên danh dự
Thành viên danh dự
Bài viết: 194
Ngày tham gia: T.Năm 19/04/2007 10:17 am
Đến từ: Đà Nẵng City
Been thanked: 1 time
Liên hệ:

Re: Thuật toán tìm kiếm string gần đúng

Gửi bàigửi bởi giongto35 » T.Bảy 12/04/2008 10:30 am

Hay thật . Tìm chuẩn quá , hết chỗ chê , :)
________________________________________________________________________________________________
. . . . . . . . . . . . .. .

vinhphuoc91
Thành viên tích cực
Thành viên tích cực
Bài viết: 146
Ngày tham gia: T.Tư 26/03/2008 5:52 pm
Đến từ: Phú Yên
Been thanked: 15 time
Liên hệ:

Re: Thuật toán tìm kiếm string gần đúng

Gửi bàigửi bởi vinhphuoc91 » T.Bảy 12/04/2008 12:20 pm

Cái này ứng dụng từ điển là ok nhất, hehe phải nhanh chóng paste nó vào chương trình của mình thôi :D Cảm ơn tienlbhoc nhiều nhá.
My website : http://tinthoitrang.net

wwwvietseo
Bài viết: 1
Ngày tham gia: CN 04/05/2008 3:57 pm
Liên hệ:

Re: Thuật toán tìm kiếm string gần đúng

Gửi bàigửi bởi wwwvietseo » CN 04/05/2008 4:19 pm

Số 30% có thể cho người dùng input vào đi Chú
http://www.bangdien.vn/
http://www.lamosi.com.vn/
http://www.vietseo.com/quangbawebsite/
http://www.highpointscity.com/h/i/g/index.asp
http://www.salutevietnam.com
http://www.rattanvina.com.vn/halinhen/HaLinh/index.php

nqtuvn
Thành viên tích cực
Thành viên tích cực
Bài viết: 112
Ngày tham gia: T.Bảy 29/03/2008 8:13 am

Re: Thuật toán tìm kiếm string gần đúng

Gửi bàigửi bởi nqtuvn » T.Tư 04/06/2008 9:47 am

em vào 2 cái links đẻ down mà ko đc/bác nào có thể gải thích cho em cái thâutj toán này 1 chút ko?
đó là biến nào là biến đc coi là từ khóa nhập vaopf đê tìm kiếm.và từ khóa này mình đem ra so sanh với chuỗi biến nào
khi em chuyển đoạn code sang vb.net nó báo lỗi trang chỉ số của mảng ở dong lệnh này

If (i + k < s.Length) And s(i + k) = s1(j) Then

tienlbhoc
Thành viên tâm huyết
Thành viên tâm huyết
Bài viết: 415
Ngày tham gia: T.Bảy 14/07/2007 10:06 pm
Đến từ: Hà Nội
Been thanked: 1 time

Re: Thuật toán tìm kiếm string gần đúng

Gửi bàigửi bởi tienlbhoc » T.Tư 04/06/2008 12:51 pm

Khi tạo class thì hàm tạo yêu cầu nhập s là từ ban đầu để so sánh như ở ảnh trên cùng là "mecury", tạo lần đầu thôi, các lần sau thì khi gọi hàm so sánh chỉ phải nhập s1 , tương ứng với các từ trong từ điển a, b,c .... duyệt từ đầu đến cuối từ điển là được :) , tốc độ không chậm đâu , nhìn hình trên đi, xem mất mấy giây.
Còn vb thì không biết, bạn convert thế nào ai chịu trách nhiệm chứ :D , đi hỏi mấy mem vb đi , tớ code c#
Diễn đàn và blog phần mềm tự làm :
http://my.opera.com/DienDanTienlbhoc/forums/
http://my.opera.com/tienlbhoc/blog/

MrB
Thành viên tích cực
Thành viên tích cực
Bài viết: 158
Ngày tham gia: T.Tư 26/03/2008 7:03 pm
Been thanked: 1 time

Re: Thuật toán tìm kiếm string gần đúng

Gửi bàigửi bởi MrB » T.Tư 04/06/2008 6:49 pm

Mình thấy nó hơi dài.

Xem cái này:
viewtopic.php?f=51&t=1830

tienlbhoc
Thành viên tâm huyết
Thành viên tâm huyết
Bài viết: 415
Ngày tham gia: T.Bảy 14/07/2007 10:06 pm
Đến từ: Hà Nội
Been thanked: 1 time

Re: Thuật toán tìm kiếm string gần đúng

Gửi bàigửi bởi tienlbhoc » T.Tư 04/06/2008 9:06 pm

Không rõ cái của bạn cái format có ý nghĩa gì nhưng cái này test sai toét :)) . Không dễ vậy đâu bạn ạ ;) , mình nghĩ cái này mất mấy ngày mới ra đấy, không thể 1 sớm 1 chiều lật đổ được đâu ;))

Mã: Chọn hết

  1. public class Test
  2. {
  3.     public static void Main()
  4.     {
  5.         Console.Write(CompareStringNotExact("mecury", "mesury").ToString());
  6.         Console.ReadLine();
  7.     }
  8.     public static int CompareStringNotExact(string s1, string s2)
  9.     {
  10.         Regex regex = new Regex(string.Format("[{0}]+", s1),
  11.             RegexOptions.IgnoreCase);
  12.         Match m = regex.Match(s2);
  13.         return m.Length;
  14.     }
  15. }
Diễn đàn và blog phần mềm tự làm :
http://my.opera.com/DienDanTienlbhoc/forums/
http://my.opera.com/tienlbhoc/blog/

battangbatgiam
Bài viết: 1
Ngày tham gia: T.Ba 18/11/2008 9:34 pm

Re: Thuật toán tìm kiếm string gần đúng

Gửi bàigửi bởi battangbatgiam » T.Năm 20/11/2008 8:15 pm

Chao tienlbhoc
Tình cờ thấy trang này cũng có tool "English word matcher" tìm từ gần đúng

"Similar is a program which finds the most similar english word for a mis-spelled word. Keyword: match similar English search difference typo word spell sound Levenshtein soundex"

http://sourceforge.net/project/showfile ... e_id=96489

bạn xem họ dùng thuật toán gì mà mỗi lần tìm một từ ra nhiều kết quả lắm, hình như là không đếm số character tương ứng thì phải.
8-)

minhdien2
Bài viết: 3
Ngày tham gia: T.Năm 23/04/2009 12:32 pm

Re: Thuật toán tìm kiếm string gần đúng

Gửi bàigửi bởi minhdien2 » T.Năm 07/01/2010 5:06 pm

làm thế nào để tính thời gian tìm kiếm hay vậy ! Chỉ mình với

tienlbhoc
Thành viên tâm huyết
Thành viên tâm huyết
Bài viết: 415
Ngày tham gia: T.Bảy 14/07/2007 10:06 pm
Đến từ: Hà Nội
Been thanked: 1 time

Re: Thuật toán tìm kiếm string gần đúng

Gửi bàigửi bởi tienlbhoc » T.Năm 07/01/2010 5:50 pm

xem qua thấy
  1. const struct qstr common_sufix[] = {
  2.     {"s", 1},
  3.     {"ing", 3},
  4.     {"ed", 2},
  5.     {"d", 1},
  6.     {"ly", 2},
  7.     {"y", 1},
  8.     {"r", 1},
  9.     {"e", 1},
  10.     {"t", 1},
  11.     {"ness", 4},
  12.     {"on", 2},
  13.     {"n", 1},
  14.     {"st", 2},
  15.     {"ve", 2},
  16.     {"le", 2},
  17.     {"l", 1},
  18.     {"er", 2},
  19.     {"or", 2},
  20.     {"te", 2},
  21.     {"ng", 2},
  22.     {"es", 2},
  23.     {"al", 2},
  24.     {"o", 1},
  25.     {"k", 1},
  26.     {"g", 1},
  27.     {"ic", 2},
  28.     {"en", 2},
  29.     {"ment", 4},
  30.     {"p", 1},
  31.     {"able", 4},
  32.     {"ion", 3},
  33.     {"man", 3},
  34. };

nó lưu các tiền tố và hậu tố của tiếng anh -> cái này chỉ chuyên tiếng anh thôi , cái của tớ dùng được chung cho nhiều ngôn ngữ (dùng tiếng việt cũng chơi được) . Mà cái này search không tốt , nếu đã chuyên tiếng anh thì cities nó phải ra city có trong kết quả -> chưa thấy nó hơn của tớ chỗ nào mà lại chỉ mỗi tiếng anh :D (cái của tớ cũng không ra city vì nó sai khác đến 3 ký tự :D nhưng đây là hàng chuyên tiếng anh có xét hậu tố nếu tớ lập trình thì nó sẽ check được ngay :)
Tính thời gian thì lấy thời gian hệ thống lúc sau - thời gian hệ thống lúc đầu là được :)
Diễn đàn và blog phần mềm tự làm :
http://my.opera.com/DienDanTienlbhoc/forums/
http://my.opera.com/tienlbhoc/blog/

minhdien2
Bài viết: 3
Ngày tham gia: T.Năm 23/04/2009 12:32 pm

Re: Thuật toán tìm kiếm string gần đúng

Gửi bàigửi bởi minhdien2 » T.Bảy 09/01/2010 2:13 am

như mình muốn tìm kiếm 1 chuỗi đó trong database và so sánh là gần đúng nhất thì cho ra kết quả đầu tiên ,còn ngược lại thì cho kết sau theo sau nó , giống google thì làm thế nào vậy !

tienlbhoc
Thành viên tâm huyết
Thành viên tâm huyết
Bài viết: 415
Ngày tham gia: T.Bảy 14/07/2007 10:06 pm
Đến từ: Hà Nội
Been thanked: 1 time

Re: Thuật toán tìm kiếm string gần đúng

Gửi bàigửi bởi tienlbhoc » T.Bảy 09/01/2010 9:07 am

Mấy cái đó pro quá , bạn phải tự phát triển thêm thôi , thuật toán của mình chỉ dừng ở đây :D , chắc bạn phải tính phần trăm đúng theo 1 cơ chế tính điểm nào đó rồi sort kết quả theo mã % đó , google trông đơn giản nhưng muốn được như nó thì không dễ à nhe :-S
Diễn đàn và blog phần mềm tự làm :
http://my.opera.com/DienDanTienlbhoc/forums/
http://my.opera.com/tienlbhoc/blog/

ad23
Thành viên chính thức
Thành viên chính thức
Bài viết: 24
Ngày tham gia: T.Sáu 23/05/2008 4:47 pm

Re: Thuật toán tìm kiếm string gần đúng

Gửi bàigửi bởi ad23 » T.Tư 20/01/2010 12:08 pm

hì hì, bắt quả tang bác tiếp tay cho bè lũ giải mã!

BDK
Thành viên chính thức
Thành viên chính thức
Bài viết: 15
Ngày tham gia: T.Tư 23/12/2009 8:24 am

Re: Thuật toán tìm kiếm string gần đúng

Gửi bàigửi bởi BDK » T.Tư 29/09/2010 10:51 pm

  1.         public static void Main()
  2.         {
  3.             ApproximatString a = new ApproximatString("(Everything I Do) I Do It For You (Featuring LeAnn Rimes)");
  4.             Console.WriteLine(a.SoSanh( "One Man's Poison (Another Man's Sweetness)"));
  5.             Console.ReadKey();
  6.         }
  7.  


Nó ra True !?!

BDK
Thành viên chính thức
Thành viên chính thức
Bài viết: 15
Ngày tham gia: T.Tư 23/12/2009 8:24 am

Re: Thuật toán tìm kiếm string gần đúng

Gửi bàigửi bởi BDK » T.Năm 30/09/2010 8:59 am

Refer to Fuzzy String Matching algorithm of Levenshtein at http://www.merriampark.com/ld.htm
  1. using System;
  2.  
  3. // <!-- m --><a class="postlink" href="http://www.merriampark.com/ld.htm">http://www.merriampark.com/ld.htm</a><!-- m -->
  4. static class LevenshteinDistance
  5. {
  6.     /// <summary>
  7.     /// Gets the similarity between two strings.
  8.     /// All relation scores are in the [0, 1] range,
  9.     /// which means that if the score gets a maximum value (equal to 1)
  10.     /// then the two string are absolutely similar
  11.     /// </summary>
  12.     /// <param name="string1">The string1.</param>
  13.     /// <param name="string2">The string2.</param>
  14.     /// <returns></returns>
  15.     public static float CalculateSimilarity(String s1, String s2)
  16.     {
  17.         if (string.IsNullOrEmpty(s1) || string.IsNullOrEmpty(s2)) return 0;
  18.  
  19.         float dis = LevenshteinDistance.Compute(s1, s2);
  20.         float maxLen = Math.Max(s1.Length, s2.Length);
  21.         return (maxLen == 0) ? 1: 1 - dis / maxLen;
  22.     }
  23.     /// <summary>
  24.     /// Compute the distance between two strings.
  25.     /// </summary>
  26.     public static int Compute(string s, string t)
  27.     {
  28.         int n = s.Length;
  29.         int m = t.Length;
  30.         int[,] d = new int[n + 1, m + 1];
  31.  
  32.         // Step 1
  33.         if (n == 0) return m;
  34.  
  35.         if (m == 0) return n;
  36.  
  37.         // Step 2
  38.         for (int i = 0; i <= n; d[i, 0] = i++)
  39.         { }
  40.  
  41.         for (int j = 0; j <= m; d[0, j] = j++)
  42.         { }
  43.  
  44.         // Step 3
  45.         for (int i = 1; i <= n; i++)
  46.         {
  47.             //Step 4
  48.             for (int j = 1; j <= m; j++)
  49.             {
  50.                 // Step 5
  51.                 int cost = (t[j - 1] == s[i - 1]) ? 0 : 1;
  52.  
  53.                 // Step 6
  54.                 d[i, j] = Math.Min(
  55.                     Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1),
  56.                     d[i - 1, j - 1] + cost);
  57.             }
  58.         }
  59.         // Step 7
  60.         return d[n, m];
  61.     }
  62. }
  63.  

songnuocbien
Bài viết: 1
Ngày tham gia: T.Bảy 06/02/2010 12:47 pm

Re: Thuật toán tìm kiếm string gần đúng

Gửi bàigửi bởi songnuocbien » T.Bảy 30/10/2010 10:41 am

thanks!


Quay về “Cấu trúc dữ liệu và giải thuật”

Đang trực tuyến

Đang xem chuyên mục này: Không có thành viên nào trực tuyến.3 khách