English | Vietnamese
 

banner

[Rule] Rules  [Home] Main Forum  [Portal] Portal  
[Members] Member Listing  [Statistics] Statistics  [Search] Search  [Reading Room] Reading Room 
[Register] Register   [Login] Login [  http  | https  ]
 
Forum Index Thảo luận hệ điều hành Windows Hỏi về thuật toán tìm kiếm?  XML
  [Question]   Hỏi về thuật toán tìm kiếm? 11/04/2008 23:31:43 (+0700) | #1 | 124636
bokinhvan_gl
Member
[Minus]    0    [Plus]
Joined: 19/07/2007 10:32:21
Messages: 95
Location: ngày hôm qua
Offline
[Profile] [PM] [Yahoo!]
Cho mình hỏi muốn tìm kiếm các chủ đề mà ký tự Unicode và ko phải Unicode thì phải làm thế nào?
VD:trog ô tìm kiếm đánh chữ: "dien dan" thì kết quả vừa có "dien dan..." và "diễn đàn..."
[Up] [Print Copy]
  [Question]   Re: Hỏi về thuật toán tìm kiếm? 12/04/2008 03:43:34 (+0700) | #2 | 124668
[Avatar]
 learn2hack
Elite Member
[Minus]    0    [Plus]
Joined: 29/06/2006 16:32:37
Messages: 825
Offline
[Profile] [PM] [WWW]
Bạn thử lập 1 danh sách những từ có dấu gắn với từ không dấu, sau đó mỗi lần query trên 1 từ khóa nào đó thì tìm trong danh sách những từ cùng nhóm và query luôn với chúng. Cách này khá mệt khi lập danh sách, nhưng mà mình chưa có cách nào để bắt máy tính nhận diện 1 từ không dấu và 1 từ có dấu cùng nghĩa vì đôi khi từ 1 từ không dấu có thể suy ra được nhiều từ có dấu khác nhau.
Blog: http://hontap.blogspot.com
Tải phần mềm miễn phí: http://www.taiphanmem.org
[Up] [Print Copy]
  [Question]   Re: Hỏi về thuật toán tìm kiếm? 12/04/2008 09:21:45 (+0700) | #3 | 124736
[Avatar]
 vivashadow
Member
[Minus]    0    [Plus]
Joined: 08/01/2008 12:36:49
Messages: 95
Offline
[Profile] [PM]
Nếu lập danh sách thì quá mất công sức, mình nghĩ sao không tận dụng một tự điển tiếng việt để tìm ra các từ có dấu tương đồng.
Hướng đi là: Với 1 từ khóa s_key (có dấu hay không dấu) ta lọc ra các từ trong tự điển s_dic với dk: bodau(s_dic) = bodau(s_key).
[Up] [Print Copy]
  [Question]   Re: Hỏi về thuật toán tìm kiếm? 12/04/2008 09:49:57 (+0700) | #4 | 124739
[Avatar]
 keyboardDigger
Member
[Minus]    0    [Plus]
Joined: 27/03/2008 16:45:48
Messages: 26
Offline
[Profile] [PM]
Bạn viết một đoạn script để tự động sinh list các từ có thể có, như vậy có lẽ sẽ "nhàn" hơn 1 chút chăng? Số lượng tổ hợp của các từ liên quan chắc chắn là không thể nhiều. Tớ không viết để chạy thử, nhưng có thể diễn giải bằng mã giả dưới đây (Trông nó như thể C++, nhưng lại giông giống JavaScript. Thông cảm, bệnh nghề nghiệp mà smilie).

Nguyên tắc của nó rất giản dị: thử từng vị trí ký tự, thay nó bằng tất cả các trường hợp chữ cái tiếng Việt liên quan. Sử dụng đệ quy kiểu sinh tổ hợp lặp là một cách làm đơn giản và tiện lợi nhất. Bạn nào hay làm đệ quy thì sẽ thấy cái này chẳng có gì xa lạ cả.

Đầu tiên, ta hard code một bảng nguyên âm và phụ âm đặc biệt của tiếng Việt (việc này nhẹ hều):
Code:
char[][] related;  // Mảng lưu trữ các ký tự liên quan đến 1 ký tự cho trước
related["a"][0] = "a"; // Chú ý: ký tự đầu tiên có liên quan là chính nó
related["a"][1] = "ă";
related["a"][2] = "â";
related["a"][3] = "á";
...
related["d"][1] = "d";
related["d"][1] = "đ";
related["d"][2] = "Đ";
related[“Đ”] = related[“d”]; // Tham chiếu ngược cho nhanh
related[“đ”] = related[“d”]; // Tham chiếu ngược tiếp 
related[“D”] = related[“d”];  // Chú ý chữ hoa chữ thường, nếu bạn đã xử lý
                                         // query rồi thì thôi làm dòng này cho tiết kiệm
...

string[]  resultList; // Mảng kết quả sau cùng
string temp; // Chuỗi lưu kết quả tạm thời
string currentWord; // Biến toàn cục lưu từ khóa đang được search hiện thời

// Gọi hàm này để lấy danh sách từ
function generateRelatedWordList(string word) {
    resultList = new string[100000]; // Bạn tự ước lượng kích thước max mong muốn
    currentWord = word;
    temp = new char[255]; // Khởi động chuỗi lưu kết quả
    buildWord(0);
    return resultList;
}

// Hàm đệ quy: i là vị trí hiện tại đang viết thử trong xâu tạm - temp
function buildWord(int i) {
    if (i == currentWord.length)    // Khi đứng ở vị trí cuối xâu - đã tìm xong 1 từ
        resultList.push(temp); //   thì đẩy nó vào mảng kết quả
    else {
        for (int j= 0; j < related[currentWord[i]].length ; j++) {
              temp[i] = related[currentWord[i]][j]; // Viết thêm 1 chữ vào vị trí hiện tại
              buildWord(i+1); // Gọi đệ quy để viết tiếp kí tự sau
        }
}


Nói như bạn vivashadow là rất có lý, vấn đề là lấy đâu ra cái từ điển "hỏi 1 cái là giả nhời" như thế bao giờ? Phải tự build lấy thôi. Nếu bạn muốn giữ lại loạt kết quả của những từ phổ biến để tăng tốc chương trình thì cứ chạy hàm generateRelatedWordList() nhiều lần và save kết quả vào chỗ mình thích là xong.
Hy vọng bạn thấy đoạn code mã giả trên là có ích smilie
Thấy vui mỗi lần nhận ra mình có thể viết lại sản phẩm trong quá khứ hiệu quả và gọn gàng hơn 1 nửa
[Up] [Print Copy]
  [Question]   Re: Hỏi về thuật toán tìm kiếm? 12/04/2008 16:27:28 (+0700) | #5 | 124774
[Avatar]
 learn2hack
Elite Member
[Minus]    0    [Plus]
Joined: 29/06/2006 16:32:37
Messages: 825
Offline
[Profile] [PM] [WWW]
Ừ, làm theo cách của 2 bạn đều ổn. Nếu dùng cách của keyboardDigger thì hơi khó lọc các từ vô nghĩa khi tổ hợp các chữ cái, các của vivashadow cũng vậy. Nhưng mình thấy thế cũng ổn rồi, nếu chi tiết hơn nữa thì có lẽ chúng ta lấn sân quá sang lĩnh vực xử lí tiếng Việt rồi, không cần thiết đến mức đó smilie.

Chúng ta có thể cải tiến 1 chút cho nó hoạt động tốt hơn:
- Dùng script trên (hoặc tương tự) sinh ra các từ 'cùng mẫu' mỗi khi user query, rồi lưu trữ kết quả trong CSDL
- Lần sau nếu user query vào nó thì lấy trong CSDL ra cho nhanh
Thỉnh thoảng rảnh rỗi thì ngồi xóa 1 vài từ vô nghĩa trong CSDL cho nhẹ và thích hợp hơn smilie
Blog: http://hontap.blogspot.com
Tải phần mềm miễn phí: http://www.taiphanmem.org
[Up] [Print Copy]
  [Question]   Re: Hỏi về thuật toán tìm kiếm? 13/04/2008 01:43:37 (+0700) | #6 | 124818
[Avatar]
 vivashadow
Member
[Minus]    0    [Plus]
Joined: 08/01/2008 12:36:49
Messages: 95
Offline
[Profile] [PM]

keyboardDigger wrote:
Bạn viết một đoạn script để tự động sinh list các từ có thể có, như vậy có lẽ sẽ "nhàn" hơn 1 chút chăng? Số lượng tổ hợp của các từ liên quan chắc chắn là không thể nhiều. Tớ không viết để chạy thử, nhưng có thể diễn giải bằng mã giả dưới đây (Trông nó như thể C++, nhưng lại giông giống JavaScript. Thông cảm, bệnh nghề nghiệp mà smilie).

Nguyên tắc của nó rất giản dị: thử từng vị trí ký tự, thay nó bằng tất cả các trường hợp chữ cái tiếng Việt liên quan. Sử dụng đệ quy kiểu sinh tổ hợp lặp là một cách làm đơn giản và tiện lợi nhất. Bạn nào hay làm đệ quy thì sẽ thấy cái này chẳng có gì xa lạ cả.

Nói như bạn vivashadow là rất có lý, vấn đề là lấy đâu ra cái từ điển "hỏi 1 cái là giả nhời" như thế bao giờ? Phải tự build lấy thôi. Nếu bạn muốn giữ lại loạt kết quả của những từ phổ biến để tăng tốc chương trình thì cứ chạy hàm generateRelatedWordList() nhiều lần và save kết quả vào chỗ mình thích là xong.
Hy vọng bạn thấy đoạn code mã giả trên là có ích smilie 


Cách này hạn chế là nó đưa ra luôn các từ vô nghĩa, cách này cũng có thể phát triển bằng cách tra trong tự điển như cách mình nói ở trên smilie .
Vđề từ điển thì kiếm một tự điển mở việt anh, việt anh để đầu mục từ tv được nhiều.
http://www.informatik.uni-leipzig.de/~duc/Dict/install.html
Cách này thậm chí có thể mở rộng để tìm các từ liên quan tiếng anh luôn smilie


[Up] [Print Copy]
  [Question]   Re: Hỏi về thuật toán tìm kiếm? 13/04/2008 03:32:55 (+0700) | #7 | 124836
[Avatar]
 vivashadow
Member
[Minus]    0    [Plus]
Joined: 08/01/2008 12:36:49
Messages: 95
Offline
[Profile] [PM]

learn2hack wrote:
Ừ, làm theo cách của 2 bạn đều ổn. Nếu dùng cách của keyboardDigger thì hơi khó lọc các từ vô nghĩa khi tổ hợp các chữ cái, các của vivashadow cũng vậy. Nhưng mình thấy thế cũng ổn rồi, nếu chi tiết hơn nữa thì có lẽ chúng ta lấn sân quá sang lĩnh vực xử lí tiếng Việt rồi, không cần thiết đến mức đó smilie.

Chúng ta có thể cải tiến 1 chút cho nó hoạt động tốt hơn:
- Dùng script trên (hoặc tương tự) sinh ra các từ 'cùng mẫu' mỗi khi user query, rồi lưu trữ kết quả trong CSDL
- Lần sau nếu user query vào nó thì lấy trong CSDL ra cho nhanh
Thỉnh thoảng rảnh rỗi thì ngồi xóa 1 vài từ vô nghĩa trong CSDL cho nhẹ và thích hợp hơn smilie
 

Cách của mình cũng vậy là sao? check trong đầu mục từ của tự điển xong thì nó nhất định phải có nghĩa chứ.

Không tra tự điển là không ổn tí nào. Theo cách của keyboardDigger thì từ vô nghĩa quá nhiều.
VD chữ dien dan: (d|đ)+i+((e|ê)*(/\~?._))+n+ + (d|đ)+ (a*(/\~?._)) + n sơ sơ cũng 2x 2 x 6 x 2 x 6 = 200 mấy mẫu trong đó chỉ có vài từ có nghĩa thôi. Ngồi lọc tay là không khả thi.
[Up] [Print Copy]
  [Question]   Re: Hỏi về thuật toán tìm kiếm? 14/04/2008 04:18:51 (+0700) | #8 | 125043
[Avatar]
 nhl294
Member
[Minus]    0    [Plus]
Joined: 17/03/2008 14:42:30
Messages: 2
Offline
[Profile] [PM]
Mình có 1 ý tưởng thế này (nhưng để có thuật toán làm thì chắc k dễ lắm), bạn chỉ cần convert toàn bộ dữ liệu của vùng được search từ có dấu thành k dấu (cái này có bạn làm rùi), sau đó bắt đầu search, kết quả trả về sẽ tương ứng với kết quả đã được convert. Mình chưa thử, nhug thiết nghĩ cách này được, k lo việc search ra từ vô nghĩa.
P/s : Trang google cũng search dc tất cả các từ đó thui ^_^ (Mình ví dụ thui)
[Up] [Print Copy]
[digg] [delicious] [google] [yahoo] [technorati] [reddit] [stumbleupon]
Go to: 
 Users currently in here 
1 Anonymous

Powered by JForum - Extended by HVAOnline
 hvaonline.net  |  hvaforum.net  |  hvazone.net  |  hvanews.net  |  vnhacker.org
1999 - 2013 © v2012|0504|218|