Tìm các từ trong một chuỗi ký tự dài. Tự động mã hóa

Question

Bạn sẽ tìm thấy các từ chính xác trong một chuỗi ký tự dài như thế nào?

Input:

"The revised report onthesyntactictheoriesofsequentialcontrolandstate" 

của Google Output:

"The revised report on syntactic theories sequential controlandstate" 

(mà là gần đủ cân nhắc thời gian mà họ sản xuất sản lượng)

Bạn nghĩ thế nào Google làm điều đó? Bạn sẽ tăng độ chính xác như thế nào?

Answer 1

tôi sẽ cố gắng một thuật toán đệ quy như thế này:

• Thử chèn dấu cách vào mỗi vị trí. Nếu phần bên trái là một từ, sau đó lặp lại ở phần bên phải.
• Đếm số từ/số từ hợp lệ trong tổng số các kết quả cuối cùng. Người có tỷ lệ tốt nhất có thể là câu trả lời của bạn.

Ví dụ, cho nó "thesentenceisgood" sẽ chạy:

thesentenceisgood 
the sentenceisgood 
    sent enceisgood 
     enceisgood: OUT1: the sent enceisgood, 2/3 
    sentence isgood 
      is good 
       go od: OUT2: the sentence is go od, 4/5 
      is good: OUT3: the sentence is good, 4/4 
    sentenceisgood: OUT4: the sentenceisgood, 1/2 
these ntenceisgood 
     ntenceisgood: OUT5: these ntenceisgood, 1/2 

Vì vậy, bạn sẽ chọn OUT3 là câu trả lời.

Answer 2

Kiểm tra thuật toán sửa lỗi chính tả. Đây là liên kết đến một bài viết về thuật toán được sử dụng trong google - http://www.norvig.com/spell-correct.html. Ở đây bạn sẽ tìm thấy a scientific paper on this topic from google.

Answer 3

Đây là một mã trong Mathematica Tôi bắt đầu phát triển cho một sân golf mã gần đây.
Đó là thuật toán tối thiểu, không tham lam, đệ quy. Điều đó có nghĩa rằng câu "bút là mighter hơn thanh kiếm" (không có khoảng trắng) trả về { "bút là sức er hơn sword} :)

findAll[s_] := 
    Module[{a = s, b = "", c, sy = "="}, 
    While[ 
    StringLength[a] != 0, 
    j = ""; 
    While[(c = findFirst[a]) == {} && StringLength[a] != 0, 
    j = j <> StringTake[a, 1]; 
    sy = "~"; 
    a = StringDrop[a, 1]; 
    ]; 
    b = b <> " " <> j ; 
    If[c != {}, 
    b = b <> " " <> c[[1]]; 
    a = StringDrop[a, StringLength[c[[1]]]]; 
    ]; 
    ]; 
    Return[{StringTrim[StringReplace[b, " " -> " "]], sy}]; 
] 

findFirst[s_] := 
    If[s != "" && (c = DictionaryLookup[s]) == {}, 
    findFirst[StringDrop[s, -1]], Return[c]]; 

Sample Input

ss = {"twodreamstop", 
     "onebackstop", 
     "butterfingers", 
     "dependentrelationship", 
     "payperiodmatchcode", 
     "labordistributioncodedesc", 
     "benefitcalcrulecodedesc", 
     "psaddresstype", 
     "ageconrolnoticeperiod", 
     "month05", 
     "as_benefits", 
     "fname"} 

Output

twodreamstop    = two dreams top 
onebackstop    = one backstop 
butterfingers    = butterfingers 
dependentrelationship  = dependent relationship 
payperiodmatchcode  = pay period match code 
labordistributioncodedesc ~ labor distribution coded es c 
benefitcalcrulecodedesc ~ benefit c a lc rule coded es c 
psaddresstype    ~ p sad dress type 
ageconrolnoticeperiod  ~ age con rol notice period 
month05     ~ month 05 
as_benefits    ~ as _ benefits 
fname      ~ f name 

HTH

Answer 4

Thử thường xuyên ngữ pháp ngẫu nhiên (tương đương với mô hình Markov ẩn) với các quy tắc sau:

for every word in a dictionary: 
stream -> word_i stream with probability p_w 
word_i -> letter_i1 ...letter_in` with probability q_w (this is the spelling of word_i) 
stream -> letter stream with prob p (for any letter) 
stream -> epsilon with prob 1 

Xác suất có thể được bắt nguồn từ một tập huấn luyện, nhưng thấy các cuộc thảo luận sau. Phân tích cú pháp có khả năng nhất được tính bằng thuật toán Viterbi, có độ phức tạp bậc hai về số lượng trạng thái ẩn, trong trường hợp này là từ vựng của bạn, vì vậy bạn có thể gặp vấn đề về tốc độ với từ vựng lớn. Nhưng nếu bạn đặt tất cả p_w = 1, q_w = 1 p = .5 Có nghĩa là, đây là xác suất trong mô hình ngôn ngữ nhân tạo, trong đó tất cả các từ đều có khả năng giống nhau và tất cả các từ không đều có khả năng giống nhau. Tất nhiên bạn có thể phân đoạn tốt hơn nếu bạn không sử dụng đơn giản hóa này, nhưng độ phức tạp của thuật toán sẽ giảm đi một chút. Nếu bạn nhìn vào mối quan hệ lặp lại trong wikipedia entry bạn có thể thử và đơn giản hóa nó cho trường hợp đặc biệt này.Xác suất phân tích cú pháp viterbi lên đến vị trí k có thể được đơn giản hóa thành VP(k) = max_l(VP(k-l) * (1 if text[k-l:k] is a word else .5^l) Bạn có thể liên kết l với chiều dài tối đa của một từ và tìm xem một chữ cái có tạo thành một từ có tìm kiếm băm hay không. Sự phức tạp của điều này là độc lập với kích thước từ vựng và là O(<text length> <max l>). Xin lỗi đây không phải là một bằng chứng, chỉ là một bản phác thảo nhưng sẽ giúp bạn đi. Một tối ưu hóa tiềm năng khác, nếu bạn tạo một trie của từ điển, bạn có thể kiểm tra xem chuỗi con có phải là tiền tố của bất kỳ từ đúng nào không. Vì vậy, khi bạn truy vấn văn bản [k-l: k] và nhận được câu trả lời phủ định, bạn đã biết rằng điều này cũng đúng cho văn bản [k-l: k + d] cho bất kỳ d nào. Để tận dụng lợi thế này, bạn sẽ phải sắp xếp lại đệ quy một cách đáng kể, vì vậy tôi không chắc chắn điều này có thể được khai thác đầy đủ (nó có thể xem bình luận).

Answer 5

Sau khi thực hiện phân tích đệ quy và tra cứu từ điển, để tăng chất lượng của các cặp từ trong cụm từ của bạn, bạn có thể quan tâm đến việc sử dụng thông tin lẫn nhau của các cặp Word.

Điều này chủ yếu là mặc dù tập huấn luyện và tìm ra M.I. giá trị của các cặp từ cho bạn biết rằng Albert Simpson ít có khả năng hơn Albert Einstein :)

Bạn có thể thử tìm kiếm Science Direct cho các tài liệu học thuật trong chủ đề này. Để biết thông tin cơ bản về thông tin Mutual, hãy xem http://en.wikipedia.org/wiki/Mutual_information

Năm ngoái tôi đã tham gia vào phần tìm kiếm cụm từ của dự án công cụ tìm kiếm mà tôi đang cố gắng phân tích tập dữ liệu wikipedia và xếp hạng từng cặp từ. Tôi đã có mã trong C + + nếu bạn quan tâm có thể chia sẻ nó với bạn nếu bạn có thể tìm thấy một số sử dụng của nó. Nó phân tích cú pháp wikimedia và cho mỗi cặp từ tìm ra thông tin lẫn nhau.