문자열을 단어로 분할하는 방법. 예 : "stringintowords"-> "문자열을 단어로"?

Question

문자열을 단어로 분할하는 올바른 방법은 무엇입니까? 는 예를 들어

(문자열은 공백이나 문장 부호가 포함되어 있지 않습니다) : "stringintowords을"-> "단어로 문자열"

여기에 사용해야 어떤 알고리즘 조언을 주실 수 있습니까?

! 업데이트 :이 질문은 단지 호기심이라고 생각하는 사람들에게. 이 알고리즘은 도메인 이름 ("sportandfishing .com"-> "SportAndFishing .com")을 캡쳐하는 데 사용될 수 있으며이 algo는 현재 aboutus dot org에서이 변환을 동적으로 수행하는 데 사용됩니다.

Answer 1

여기 많은 사람들이 언급했듯이 이것은 표준의 쉬운 동적 프로그래밍 문제입니다. 가장 좋은 해결책은 Falk Hüffner입니다.추가 정보 :

(a) isWord을 trie로 구현하는 것을 고려해야합니다. 올바르게 사용하면 (단어를 점진적으로 테스트하여) 많은 시간을 절약 할 수 있습니다.

(b) "segmentation dynamic programming"을 입력하면 대학 코드 수준의 강의 코드에서 this lecture at Duke's과 같은 의사 코드 알고리즘을 사용하여보다 자세한 답변을 얻을 수 있습니다 (이는 확률 론적 접근 방식을 제공하기까지합니다). 사전에 포함되지 않을 단어가있을 때해야할 일).

Answer 2

최상의 방법은 사전과 0의 하위 문자열을 비교하고 일치 항목을 찾으면 해당 단어를 추출하고 그 지점에서 새 사전 검색을 시작하는 것이지만 오류가 발생하기 쉽습니다. 복수형 및 아포스트로피 (싱크대, 싱크대) 및 기타 품사와 관련된 문제가 발생할 것입니다.

편집

"singleemotion" "하나의 감정"또는 "죄 글리 운동"이 될 것인가?

Answer 3

해당 문자열을 단어로 나눌 수있는 유일한 방법은 사전을 사용하는 것입니다. 이것은 아마도 자원 집약적 일 것입니다.

Answer 4

이것은 기본적으로 knapsack problem의 변형입니다. 따라서 Wiki에서 다루는 단어와 솔루션의 포괄적 인 목록이 필요합니다.

엄청난 크기의 사전을 사용하면 자원 집약적이며 오랜 시간 작업이 될 것이며,이 문제가 해결 될지조차 확신 할 수 없습니다.

Answer 5

가능한 단어 목록을 작성하고 긴 단어에서 짧은 단어로 정렬하십시오.

목록의 각 항목이 문자열의 첫 번째 부분과 맞는지 확인하십시오. 같으면 공백으로 제거하고 문장에 추가하십시오. 이것을 반복하십시오.

Answer 6

이 권한을 얻으려면 에이 사전 기반 접근 방식을 사용하는 것이 끔찍할만큼 비효율적입니다. 또한 알고리즘의 결과를 여러 번 받아야합니다. 예를 들어

: windowsteamblog (http://windowsteamblog.com/의 명성)

windowsteamblogwindowsteamblog

Answer 7

이에 대한 학계의 공정한 조금에게이 있어야합니다. 검색하려는 키워드는 word segmentation입니다. 예를 들어 This paper이 유망 해 보입니다.

일반적으로 markov models 및 viterbi algorithm에 대해 자세히 알아볼 수 있습니다. 후자는 가능한 모든 세분화를 철저히 테스트하지 않고 문자열에 대한 그럴듯한 세분화를 찾을 수있는 동적 프로그래밍 알고리즘입니다.여기에서 필수적인 통찰력은 첫 번째 문자에 대해 가능한 세분화가 가능하고 가장 가능성있는 세그먼테이션 만 찾고 싶다면 후속 문자에 대해이 세 가지를 모두 평가할 필요가 없습니다. 가장 가능성이있는 것.

Answer 8

isWord(w)이 있다고 가정 해보십시오. w이 사전을 사용하는 단어인지 확인합니다. 단순함을 위해서하자면, 어떤 단어가 w과 같은 분할이 가능한지 여부 만 알고 싶다고 가정하십시오. 이는 동적 프로그래밍을 통해 쉽게 수행 할 수 있습니다.

S[1..length(w)]을 부울 항목이있는 테이블로 설정하십시오. 단어 w[1..i]을 분할 할 수있는 경우 S[i]이 참입니다. 이어서

S를 계산 length(w)에 S[1] = isWord(w[1]) 및 for i=2를 [I] = (isWord [1..i] w} 또는 {2..i 임의 J 대 : S [J-1] isWord [J. .나는]).

사전 쿼리가 일정 시간 인 경우 O (길이 (w)^2) 시간이 필요합니다. 실제로 분할을 찾으려면, 참으로 설정된 각 S [i]에 승리 한 분할을 저장하십시오. 또한 이러한 모든 분할을 저장하여 모든 솔루션을 열거 할 수 있습니다.

Answer 9

주어진 문자열에 가능한 쪼개진 수를 고려하십시오. 문자열에 n자를 입력하면 n-1 개의 분할 할 수 있습니다. 예를 들어 cat 문자열의 경우 a 전에 분할 할 수 있으며 t 전에 분할 할 수 있습니다. 이로 인해 4 가지 분할이 가능합니다.

이 문제는 문자열을 분할해야하는 부분을 선택하는 것으로 볼 수 있습니다. 또한 얼마나 많은 스플릿이 있을지 선택해야합니다. 따라서 Sum(i = 0 to n - 1, n - 1 choose i) 가능한 분할이 있습니다. Binomial Coefficient Theorem에 의해 x와 y가 모두 1 인 경우 pow (2, n-1)와 같습니다.

이 계산의 대부분은 일반적인 하위 문제에 달려 있으므로 Dynamic Programming은 알고리즘의 속도를 높일 수 있습니다. 내 머리 꼭대기에서, 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을 계산하면 꽤 도움이 될 것입니다. 기하 급수적으로 가능한 세그먼트 수는 여전히 있지만 초기 분할이 단어를 형성하지 않으면 세그먼트 화를 신속하게 제거 할 수 있습니다. 그러면 솔루션은 j sub k = i sub (k + 1) 인 조건의 정수 시퀀스 (i0, j0, i1, j1, ...)가됩니다.

목표가 제대로 낙타의 URL 인 경우 문제를 회피하고 조금 더 직접적으로 설명합니다. URL 홈페이지를 가져 와서 원본 HTML에서 공백과 대소 문자를 제거하고 문자열을 검색하십시오. 일치하는 항목이 있으면 원본 HTML에서 해당 섹션을 찾아서 반환하십시오.

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

그리고 당신의 대답에서 온 것입니다 :과 같이 원래 문자열에서 발생 얼마나 많은 공백 당신은 그 선언 NumSpaces의 배열을 필요 했어 물론

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

,이 경우 휴식 것이 madduckets .com은 "Mad Duckets"을 홈페이지의 어딘가에 갖고 있지 않았습니다. 아아, 기하 급수적 인 문제를 피하기 위해 지불하는 대가입니다.

Answer 10

이것은 사전없이 (특정 정도까지) 실제로 수행 될 수 있습니다. 본질적으로, 이것은 감독되지 않은 단어 분할 문제입니다. 도메인 이름의 큰 목록을 수집하고, 감독되지 않은 분할 학습 알고리즘 (예 :)을 적용하고 새 도메인 이름에 대해 학습 된 모델을 적용해야합니다. 나는 그것이 잘 될지 모르겠다.하지만 (흥미로울 것이다).

Answer 11

나는이 문제를보고 있었고 아마 내가 어떻게했는지 공유 할 수있을 것이라고 생각했다. 그것은 즉 내 알고리즘은 그래서 어쩌면 내가 의사에 내 최적의 솔루션을 공유 할 수 설명하기 너무 어렵다 : 사실

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

,이 문제가 O(n) 시간에 해결 될 수있는 사전과 함께. 보다 정확하게는 (k + 1) * n에서 최악의 경우, n은 문자열의 문자 수이고 k은 사전에서 가장 긴 단어의 길이입니다.

게다가 알고리즘을 통해 스팸을 건너 뛸 수 있습니다. O (N^2)를 실행하는 시간이 https://gist.github.com/3381522

Answer 13

간단한 자바 솔루션 :

는 여기에 내가 몇 시간 전에 만든 커먼 리스프에서 작업을 구현합니다.

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; 
    } 
}