Cách chia chuỗi thành các từ. Ví dụ: "stringintowords" -> "String Into Words"?

Question

Cách đúng để tách chuỗi thành từ là gì? (string không chứa bất kỳ dấu cách hoặc dấu chấm câu)

Ví dụ: "stringintowords" -> "Chuỗi Into Words"

Ông có thể xin vui lòng tư vấn cho những thuật toán nên được sử dụng ở đây?

! Cập nhật: Đối với những người nghĩ câu hỏi này chỉ dành cho sự tò mò. Thuật toán này có thể được sử dụng để cam hoá tên miền ("sportandfishing .com" -> "SportAndFishing .com") và algo này hiện đang được sử dụng bởi aboutus dot org để thực hiện chuyển đổi này theo kiểu động.

Answer 1

Như đã đề cập bởi nhiều người ở đây, đây là một vấn đề lập trình tiêu chuẩn, dễ năng động: giải pháp tốt nhất được đưa ra bởi Falk Hüffner.Thông tin bổ sung mặc dù:

(a) bạn nên cân nhắc triển khai isWord bằng trie.

(b) nhập "lập trình động phân đoạn" cho điểm số câu trả lời chi tiết hơn, từ các bài giảng ở cấp đại học với thuật toán mã giả, chẳng hạn như this lecture at Duke's (thậm chí còn cung cấp cách tiếp cận xác suất đơn giản để xử lý phải làm gì khi bạn có các từ không được chứa trong bất kỳ từ điển nào).

Answer 2

Đặt cược tốt nhất là so sánh chuỗi con từ 0 với từ điển và khi bạn tìm thấy kết quả phù hợp, hãy trích xuất từ ​​đó và bắt đầu tìm kiếm từ điển mới từ điểm đó ... nhưng sẽ rất dễ xảy ra lỗi, và bạn sẽ gặp vấn đề với số nhiều và dấu nháy đơn (bồn rửa, bồn rửa) và các phần khác của lời nói.

EDIT

sẽ "singleemotion" trở thành "cảm xúc đơn" hoặc "chuyển động glee tội lỗi"?

Answer 3

Cách duy nhất mà bạn có thể tách chuỗi đó thành các từ là sử dụng từ điển. Mặc dù điều này có lẽ sẽ khá tài nguyên.

Answer 4

Điều này về cơ bản là một biến thể của knapsack problem, vì vậy những gì bạn cần là danh sách toàn diện các từ và bất kỳ giải pháp nào được đề cập trong Wiki.

Với từ điển có kích thước tương đối, điều này sẽ cực kỳ tốn nhiều tài nguyên và hoạt động lâu dài, và bạn thậm chí không thể chắc chắn rằng vấn đề này sẽ được giải quyết.

Answer 5

Tạo danh sách các từ có thể, sắp xếp từ từ dài thành các từ ngắn.

Kiểm tra xem mỗi mục nhập trong danh sách có phải là phần đầu tiên của chuỗi không. Nếu nó bằng, loại bỏ điều này và nối nó vào câu của bạn với một khoảng trắng. Lặp lại điều này.

Answer 6

Nếu bạn muốn đảm bảo rằng bạn nhận được quyền này, bạn sẽ có để sử dụng phương pháp tiếp cận dựa trên từ điển và sẽ vô cùng hiệu quả. Bạn cũng sẽ phải mong đợi để nhận được nhiều kết quả từ thuật toán của mình.

Ví dụ: windowsteamblog (của http://windowsteamblog.com/ nổi tiếng)

• windowsteamblog
• windowsteamblog

Answer 7

Nên có một chút công bằng trong các tài liệu học thuật về vấn đề này. Các từ khóa bạn muốn tìm kiếm là word segmentation. Ví dụ: This paper trông đầy hứa hẹn.

Nói chung, bạn có thể muốn tìm hiểu về markov models và viterbi algorithm. Sau đó là thuật toán lập trình động có thể cho phép bạn tìm các phân đoạn hợp lý cho chuỗi mà không kiểm tra toàn bộ mọi phân đoạn có thể có.Thông tin chi tiết cần thiết ở đây là nếu bạn có phân đoạn có thể cho các ký tự m đầu tiên và bạn chỉ muốn tìm phân đoạn có khả năng nhất, bạn không cần phải đánh giá từng phân đoạn này đối với các ký tự tiếp theo - bạn chỉ cần tiếp tục đánh giá có khả năng nhất.

Answer 8

Giả sử bạn có hàm isWord(w), kiểm tra xem w có phải là từ sử dụng từ điển hay không. Hãy để đơn giản cũng giả định cho bây giờ mà bạn chỉ muốn biết liệu một số từ w chia tách như vậy là có thể. Điều này có thể dễ dàng thực hiện với lập trình động.

Hãy để S[1..length(w)] là một bảng có mục nhập Boolean. S[i] là đúng nếu từ w[1..i] có thể được chia nhỏ. Sau đó thiết lập S[1] = isWord(w[1]) và for i=2-length(w) tính

S [i] = (isWord [w [1..i] hoặc cho bất kỳ j trong {} 2..i: S [j-1] và isWord [j. .tôi]).

Điều này có thời gian O (chiều dài (w)^2), nếu truy vấn từ điển là thời gian không đổi. Để thực sự tìm thấy phần tách, chỉ cần lưu phần chia chiến thắng trong mỗi S [i] được đặt thành true. Điều này cũng có thể được điều chỉnh để liệt kê tất cả các giải pháp bằng cách lưu trữ tất cả các phân chia đó.

Answer 9

Hãy xem xét số lượng tuyệt đối các phân tách có thể có cho một chuỗi nhất định. Nếu bạn có n ký tự trong chuỗi, có n-1 các vị trí có thể tách ra. Ví dụ: đối với chuỗi cat, bạn có thể chia trước a và bạn có thể chia trước t. Điều này dẫn đến 4 phân đoạn có thể có.

Bạn có thể xem vấn đề này là chọn nơi bạn cần chia chuỗi. Bạn cũng cần phải chọn bao nhiêu phần chia sẽ có. Vì vậy, có Sum(i = 0 to n - 1, n - 1 choose i) các phân đoạn có thể có. Bởi các Binomial Coefficient Theorem, với x và y cả hai là 1, điều này là tương đương với pow (2, n-1).

Đã cấp, rất nhiều tính toán này dựa trên các vấn đề con phổ biến, vì vậy, Dynamic Programming có thể tăng tốc thuật toán của bạn. Trên đỉnh đầu của tôi, tính toán một boolean matrix M such M[i,j] is true if and only if the substring of your given string from i to j is a word sẽ giúp đỡ khá nhiều. Bạn vẫn có một số mũ có thể phân đoạn có thể, nhưng bạn sẽ nhanh chóng có thể loại bỏ phân khúc nếu phân tách đầu không tạo thành một từ. Một giải pháp sau đó sẽ là một chuỗi các số nguyên (i0, j0, i1, j1, ...) với điều kiện là j sub k = i sub (k + 1).

Nếu mục tiêu của bạn đúng là URL trường hợp lạc đà, tôi sẽ bỏ qua vấn đề và trực tiếp tìm hiểu thêm: Nhận trang chủ cho URL, xóa mọi khoảng trắng và viết hoa khỏi HTML nguồn và tìm kiếm chuỗi của bạn. Nếu có kết quả phù hợp, hãy tìm phần đó trong HTML gốc và trả lại. Bạn sẽ cần một mảng của NumSpaces khai báo bao nhiêu khoảng trắng xảy ra trong chuỗi ban đầu như vậy:

Needle:  isashort  
Haystack:  This is a short phrase  
Preprocessed: thisisashortphrase 
NumSpaces : 000011233333444444 

Và câu trả lời của bạn sẽ đến từ:

location = prepocessed.Search(Needle) 
locationInOriginal = location + NumSpaces[location] 
originalLength = Needle.length() + NumSpaces[location + needle.length()] - NumSpaces[location] 
Haystack.substring(locationInOriginal, originalLength) 

Tất nhiên, điều này sẽ phá vỡ nếu madduckets .com không có "Mad Duckets" ở đâu đó trên trang chủ. Than ôi, đó là mức giá bạn phải trả để tránh vấn đề về số mũ.

Answer 10

Điều này có thể thực sự được thực hiện (ở một mức độ nhất định) mà không cần từ điển. Về cơ bản, đây là một vấn đề phân đoạn từ không giám sát. Bạn cần thu thập danh sách tên miền lớn, áp dụng thuật toán học phân đoạn không giám sát (ví dụ:) và áp dụng mô hình đã học cho tên miền mới. Tôi không chắc nó sẽ hoạt động tốt như thế nào, mặc dù (nhưng nó sẽ rất thú vị).

Answer 11

Tôi đã xem xét vấn đề và nghĩ rằng có thể tôi có thể chia sẻ cách tôi đã làm. Đó là một chút quá khó để giải thích thuật toán của tôi trong những lời như vậy có lẽ tôi có thể chia sẻ giải pháp tối ưu hóa của tôi trong giả:

string mainword = "stringintowords"; 
array substrings = get_all_substrings(mainword); 

/** this way, one does not check the dictionary to check for word validity 
* on every substring; It would only be queried once and for all, 
* eliminating multiple travels to the data storage 
*/ 
string query = "select word from dictionary where word in " + substrings; 
array validwords = execute(query).getArray(); 

validwords = validwords.sort(length, desc); 

array segments = []; 
while(mainword != ""){ 
    for(x = 0; x < validwords.length; x++){ 
     if(mainword.startswith(validwords[x])) { 
      segments.push(validwords[x]); 
      mainword = mainword.remove(v); 
      x = 0; 
     } 
    } 

    /** 
    * remove the first character if any of valid words do not match, then start again 
    * you may need to add the first character to the result if you want to 
    */ 
    mainword = mainword.substring(1); 
} 

string result = segments.join(" "); 

Answer 12

Trên thực tế, với các từ điển vấn đề này có thể được giải quyết trong thời gian O(n). Chính xác hơn trong số (k + 1) * n ở mức tồi tệ nhất, trong đó n là số ký tự trong chuỗi và k là độ dài của từ dài nhất trong từ điển.

Bên cạnh đó, thuật toán cho phép bạn bỏ qua thư rác.

Đây là việc thực hiện làm việc trong Common Lisp tôi đã tạo ra một số thời gian trước đây: https://gist.github.com/3381522

Answer 13

Một giải pháp Java đơn giản trong đó có O (n^2) thời gian chạy.

public class Solution { 
    // should contain the list of all words, or you can use any other data structure (e.g. a Trie) 
    private HashSet<String> dictionary; 

    public String parse(String s) { 
     return parse(s, new HashMap<String, String>()); 
    } 

    public String parse(String s, HashMap<String, String> map) { 
     if (map.containsKey(s)) { 
      return map.get(s); 
     } 
     if (dictionary.contains(s)) { 
      return s; 
     } 
     for (int left = 1; left < s.length(); left++) { 
      String leftSub = s.substring(0, left); 
      if (!dictionary.contains(leftSub)) { 
       continue; 
      } 
      String rightSub = s.substring(left); 
      String rightParsed = parse(rightSub, map); 
      if (rightParsed != null) { 
       String parsed = leftSub + " " + rightParsed; 
       map.put(s, parsed); 
       return parsed; 
      } 
     } 
     map.put(s, null); 
     return null; 
    } 
}