공백/구분 기호없이 알파벳/문자열을 사전 단어로 분리하는 방법은 무엇입니까?

Question

두 개 이상의 사전 영어 단어로 구성된 문자열이 있지만 단어 사이의 공백이 없습니다. R이나 파이썬에서 단어를 어떻게 분리 할 수 ​​있습니까?

예 :

Input_string = "thequickbrownfox" 

Desired_output_string = "the quick brown fox" 

텍스트 처리를 할 수있는 알고리즘이 있습니까?

Answer 1

선형 문제는 아닙니다. 다른 어려움 중에서도 일부 문자 시퀀스는 하나 이상의 합리적인 단어 열로 분리 될 수 있습니다.

그러나이 방법은 재귀 루틴을 사용하면 간단합니다. 어휘집 (합법적 인 단어 사전)을 통해 각 단어를 찾으십시오. 주어진 문장의 시작 부분부터 구성 할 수 있습니다. 그 단어들을 반복합니다. 각각에 대해 나머지 문장을 파싱합니다. 성공하면 올바르게 분리 된 입력 (현재 단어 + 나머지를 파싱)을 반환합니다.

// Parse a character sequence 
// return a list of legal word separations 
// Assume a word list, lexicon, as a global 
sep_string(str sentence) 
    result = <empty list> 
    sent_size = length of sentence 

    for word_size in 1:sent_size 
     word = sentence[0:word_size-1] // next potential word 

     if word in lexicon 
      // Found a legal word; remove it and parse 
      // the rest of the sequence 
      sep_rest = sep_string(sentence[word_size:sent_size]) 
      // sep_rest is a list of parsings for 
      // the rest of the sequence 

      for each solution in sep_rest 
       append (word + " " + solution) to result 

    return result