Làm cách nào để phân tách văn bản đã cho thành các từ trong từ điển?

Question

Đây là câu hỏi phỏng vấn. Giả sử bạn có một chuỗi text và một số dictionary (một tập hợp các chuỗi). Làm thế nào để bạn chia nhỏ text thành các chuỗi sao cho mỗi chuỗi con được tìm thấy trong dictionary.

Ví dụ: bạn có thể chia nhỏ "thisisatext" thành ["this", "is", "a", "text"] sử dụng /usr/share/dict/words.

Tôi tin rằng thụt lùi có thể giải quyết vấn đề này (trong giả Java):

 
void solve(String s, Set<String> dict, List<String> solution) { 
    if (s.length == 0) 
     return 
    for each prefix of s found in dict 
     solve(s without prefix, dict, solution + prefix) 
} 

List<String> solution = new List<String>() 
solve(text, dict, solution) 

Liệu nó có ý nghĩa? Bạn có tối ưu hóa bước tìm kiếm các tiền tố trong từ điển không? Bạn muốn giới thiệu cấu trúc dữ liệu nào?

Answer 1

Giải pháp này giả định sự tồn tại của cấu trúc dữ liệu Trie cho từ điển. Hơn nữa, đối với mỗi nút trong Trie, giả định các chức năng sau:

1. nút.IsWord(): Trả về true nếu đường dẫn đến nút đó là một từ
2. node.IsChild (char x): Trả về true nếu có con có nhãn x
3. node.GetChild (char x): Trả về con nút với nhãn x

Function annotate(String str, int start, int end, int root[], TrieNode node): 
i = start 
while i<=end: 
    if node.IsChild (str[i]): 
     node = node.GetChild(str[i]) 
     if node.IsWord(): 
      root[i+1] = start 
     i+=1 
    else: 
     break; 

end = len(str)-1 
root = [-1 for i in range(len(str)+1)] 
for start= 0:end: 
    if start = 0 or root[start]>=0: 
     annotate(str, start, end, root, trieRoot) 

index 0 1 2 3 4 5 6 7 8 9 10 11 
str: t h i s i s a t e x t 
root: -1 -1 -1 -1 0 -1 4 6 -1 6 -1 7 

tôi sẽ rời khỏi phần để bạn có thể liệt kê những từ mà tạo nên chuỗi bằng cách ngược lại đi qua gốc.

Độ phức tạp thời gian là O (nk) trong đó n là độ dài của chuỗi và k là độ dài của từ dài nhất trong từ điển.

PS: Tôi giả định các từ sau trong từ điển: đây là, a, văn bản, đã ăn.

Answer 2

Cách tiếp cận 1- Trie có vẻ phù hợp ở đây. Tạo trie của các từ trong từ điển tiếng anh. Tòa nhà trie này là một chi phí thời gian. Sau khi trie được xây dựng sau đó string của bạn có thể dễ dàng so sánh chữ cái bằng chữ cái. nếu tại bất kỳ điểm nào bạn gặp phải một chiếc lá trong trie bạn có thể giả sử bạn tìm thấy một từ, thêm vào danh sách & tiếp tục với quá trình truyền tải của bạn. Thực hiện việc truyền tải cho đến khi bạn đến cuối số string của bạn. Danh sách là đầu ra.

Độ phức tạp của thời gian cho tìm kiếm - O (word_length).

Không gian phức tạp - O (charsize * word_length * no_words). Kích thước của từ điển của bạn.

Phương pháp tiếp cận 2 - Tôi đã nghe nói về Suffix Trees, chưa bao giờ sử dụng chúng nhưng có thể hữu ích ở đây.

Phương pháp tiếp cận 3 - là thiết bị thay thế lố bịch hơn &. bạn đã gợi ý điều này.

Bạn có thể thử theo cách khác. Chạy qua dict là kiểm tra kết nối chuỗi phụ. Ở đây tôi giả sử các phím trong số dict là words của từ điển tiếng Anh /usr/share/dict/words. Vì vậy, mã psuedo trông giống như thế này -

(list) splitIntoWords(String str, dict d) 
{ 
    words = [] 
    for (word in d) 
    { 
     if word in str 
      words.append(word); 
    } 
    return words; 
} 

Tính phức tạp - O (n) chạy qua toàn bộ dict + O (1) cho kết hợp chuỗi con.

Space - tồi tệ nhất trường hợp O (n) nếu len(words) == len(dict)

Như những người khác đã chỉ ra, điều này đòi hỏi quay lui.

Answer 3

Có một writeup rất kỹ lưỡng cho giải pháp cho vấn đề này trong này blog post.

Ý tưởng cơ bản là chỉ để memoize chức năng bạn đã viết và bạn sẽ có một O (n^2) thời gian, O (n) thuật toán không gian.

Answer 4

Bạn có thể giải quyết vấn đề này bằng cách sử dụng Dynamic Programming và Hashing.

Tính băm của mỗi từ trong từ điển. Sử dụng hàm băm bạn thích nhất. Tôi sẽ sử dụng một cái gì đó như (a1 * B^(n - 1) + a2 * B^(n - 2) + ... + một * B^0)% P, trong đó a1a2 ... an là một chuỗi, n là độ dài của chuỗi, B là cơ sở của đa thức và P là số nguyên tố lớn. Nếu bạn có giá trị băm của chuỗi a1a2 ... bạn có thể tính giá trị băm của chuỗi a1a2 ... ana (n + 1) trong thời gian không đổi: (hashValue (a1a2 ... an) * B + a (n + 1))% P.

Độ phức tạp của phần này là O (N * M), trong đó N là số từ trong từ điển và M là độ dài của từ dài nhất trong từ điển.

Sau đó, sử dụng một chức năng DP như thế này:

bool vis[LENGHT_OF_STRING]; 
    bool go(char str[], int length, int position) 
    { 
     int i; 

     // You found a set of words that can solve your task. 
     if (position == length) { 
      return true; 
     } 

     // You already have visited this position. You haven't had luck before, and obviously you won't have luck this time. 
     if (vis[position]) { 
     return false; 
     } 
     // Mark this position as visited. 
     vis[position] = true; 

     // A possible improvement is to stop this loop when the length of substring(position, i) is greater than the length of the longest word in the dictionary. 
     for (i = position; position < length; i++) { 
     // Calculate the hash value of the substring str(position, i); 
     if (hashValue is in dict) { 
      // You can partition the substring str(i + 1, length) in a set of words in the dictionary. 
      if (go(i + 1)) { 
       // Use the corresponding word for hashValue in the given position and return true because you found a partition for the substring str(position, length). 
       return true; 
      } 
     } 
     } 

     return false; 
    } 

Sự phức tạp của thuật toán này là O (N * M), trong đó N là chiều dài của chuỗi và M là độ dài của từ dài nhất trong từ điển hoặc O (N^2), tùy thuộc vào bạn có mã hóa cải tiến hay không.

Vì vậy, tổng độ phức tạp của thuật toán sẽ là: O (N1 * M) + O (N2 * M) (hoặc O (N2^2)), trong đó N1 là số từ trong từ điển, M là độ dài của từ dài nhất trong từ điển và N2 là chiều dài của chuỗi).

Nếu bạn không thể nghĩ ra hàm băm tốt (không có va chạm), giải pháp có thể khác là dùng Tries hoặc Patricia Trie (nếu kích thước của Trie bình thường là rất lớn) (Tôi có thể 't đăng liên kết cho các chủ đề này bởi vì danh tiếng của tôi không đủ cao để đăng hơn 2 liên kết). Nhưng khi bạn sử dụng điều này, độ phức tạp của thuật toán sẽ là O (N * M) * O (Thời gian cần để tìm từ trong trie), trong đó N là độ dài của chuỗi và M là độ dài của từ dài nhất trong từ điển.

Tôi hy vọng điều đó sẽ hữu ích và tôi xin lỗi vì tiếng anh nghèo của tôi.