Split String in Wörterbuchwörter und Nicht-Wörterbuch-Wörter

Question

Ich möchte eine Zeichenfolge in eine Folge von Wörtern mit einem Wörterbuch aufteilen.

Die folgende Funktion gibt mir nur Wörter mit Buchstabengrenzen.

function spltToWord(prm){ 
    var spltedAr = prm.split(/(?=[A-Z][a-z])/); 
    return spltedAr.join(" ").trim(); 
} 

Ich möchte den Text in Wörterbuch/Nicht-Wörterbuch Wörter trennen.

Zum Beispiel:

Iamno123prisoner - Ich bin nicht 123 Gefangene

USAisveryrich - USA ist sehr reich

Albertgaveme5rupees - Albert gab mir 5 Rupien

Ein Beispielwörterbuch c ein gefunden Here für refrence.

Answer 1

Wenn das Wörterbuch viele Wörter enthält, werden Sie eine schnellere Lösung wollen, als passende ein Wort zu einer Zeit gegen Teil des eingegebenen Textes. Wenn es zehntausend Wörter im Wörterbuch gibt, müssen Sie mit diesem naiven Ansatz mindestens zehntausend Zeichen vergleichen.

Eine effizientere Lösung beinhaltet die Verwendung eines trie in dem Sie die Wörter aus dem Wörterbuch gespeichert haben. Die Überprüfung, ob ein Wort im Wörterbuch vorhanden ist, erfordert nur einen einzigen Durchlauf durch die Zeichenfolge.

Ein weiterer Vorteil ist, dass Sie für die längste Match von einer bestimmten Position in dem Text beginnen zu suchen. Dieser Ansatz wird im folgenden Code-Schnipsel demonstriert, der ein kleines Wörterbuch enthält, das ausreicht, um Ihre Beispiele zu verarbeiten. Sie können dies durch Ihr eigenes Wörterbuch ersetzen, wenn Sie den Code lokal ausführen.

var Global = { 
 
    dictionary: [ 
 
    'aa', 'I', 'i', 's', 
 
    'aah', 'am', 
 
    'aahed', 'no', 
 
    'aahing', '123', 
 
    'aahs', 'prisoner', 
 
    'aal', 'USA', 
 
    'aalii', 'is', 
 
    'aaliis', 'very', 
 
    'aals', 'rich', 
 
    'aardvark', 'Albert', 
 
    'aardvarks', 'gave', 'me', '5', 'rupees' 
 
    ] 
 
}; 
 

 
function addToTrie(word) { 
 
    var node = Global.trie; 
 
    for (var pos = 0; pos < word.length; ++pos) { 
 
    var letter = word.charAt(pos); 
 
    if (node[letter] === undefined) { 
 
     node[letter] = {}; 
 
    } 
 
    node = node[letter]; 
 
    } 
 
    node.terminal = true; 
 
} 
 

 
function findLongestMatch(text, start) { 
 
    var node = Global.trie, 
 
     best = start - 1; 
 
    for (var pos = start; pos < text.length; ++pos) { 
 
    var letter = text.charAt(pos); 
 
    if (node[letter] === undefined) { 
 
     break; 
 
    } 
 
    node = node[letter]; 
 
    if (node.terminal) { 
 
     best = pos; 
 
    } 
 
    } 
 
    return best - start + 1; 
 
} 
 

 
function loadTrie() { 
 
    var words = Global.dictionary, 
 
     trie = Global.trie = {}; 
 
    words.forEach(function (word) { 
 
    addToTrie(word); 
 
    }); 
 
}; 
 

 
function println(label, s, labelStyle) { 
 
    if (s === undefined) { 
 
    s = label || ''; 
 
    } else { 
 
    var className = 'label' + (labelStyle ? ' ' + labelStyle : ''); 
 
    s = '<div class="' + className + '">' + label + '</div> ' + s; 
 
    } 
 
    document.getElementById('message').innerHTML += (s + '<br />'); 
 
} 
 

 
function process(text) { 
 
    var results = [], 
 
     letters = [], 
 
     pos = 0; 
 
    while (pos < text.length) { 
 
    var length = findLongestMatch(text, pos); 
 
    if (length == 0) { 
 
     letters.push(text.charAt(pos)); 
 
     pos += 1; 
 
    } else { 
 
     if (letters.length != 0) { 
 
     results.push({ word: letters.join(''), known: false }); 
 
     letters = []; 
 
     } 
 
     results.push({ word: text.substring(pos, pos + length), known: true }); 
 
     pos += length; 
 
    } 
 
    } 
 
    if (letters.length != 0) { 
 
    results.push({ word: letters.join(''), known: false }); 
 
    letters = []; 
 
    } 
 
    var breakdown = results.map(function (result) { 
 
    return result.word; 
 
    }); 
 
    println(); 
 
    println(' breakdown:', '/' + breakdown.join('/') + '/'); 
 
    results.forEach(function (result) { 
 
    println((result.known ? 'in dictionary' : '  unknown') + ':', 
 
     '"' + result.word + '"', (result.known ? undefined : 'unknown')); 
 
    }); 
 
}; 
 

 
window.onload = function() { 
 
    loadTrie(); 
 
    process('WellIamno123prisoner'); 
 
    process('TheUSAisveryrichman'); 
 
    process('Albertgaveme5rupeesyo'); 
 
};

body { 
 
    font-family: monospace; 
 
    color: #444; 
 
    font-size: 14px; 
 
    line-height: 20px; 
 
} 
 
.label { 
 
    display: inline-block; 
 
    width: 200px; 
 
    font-size: 13px; 
 
    color: #aaa; 
 
    text-align: right; 
 
} 
 
.label.unknown { 
 
    color: #c61c39; 
 
}

<div id="message"></div>

Answer 2

Edit # 2

var words = ["apple", "banana", "candy", "cookie", "doughnut"]; 
var input = "banana123candynotawordcookieblahdoughnut"; 
var currentWord = "", 
    result = ""; 

while (true) { 
    for (var i = 0; i < input.length; i++) { 
     currentWord += input[i]; 
     if (words.indexOf(currentWord) >= 0) { 
      result += " " + currentWord + " "; 
      currentWord = ""; 
     } 
    } 

    if (currentWord.length > 0) { 
     result += currentWord[0]; 
     input = currentWord.substr(1); 
     currentWord = ""; 
    } else { 
     break; 
    } 
} 

console.log(result.trim()); // "banana 123 candy notaword cookie blah doughnut" 

Hinweis wird das Ergebnis zwei Leerzeichen enthalten, wenn zwei aufeinander folgende Wörter aus dem Wörterbuch sind. Sie können dies mit Regex beheben.

Es ist nicht die schönste Lösung (Sie können es rekursiv machen, die lesbarer sein kann), und es bietet nicht mehrere Lösungen (siehe DP-Link im Kommentar dafür).

bearbeiten dies nicht berücksichtigt, nicht-Wörterbuch Worte nicht nehmen.

einen einfachen Greedy-Algorithmus verwenden:

var words = ["apple", "banana", "candy", "cookie", "doughnut"]; 
var input = "bananacandycookiedoughnut"; 
var currentWord = "", result = ""; 

for (var i = 0; i < input.length; i++) { 
    currentWord += input[i]; 
    if (words.indexOf(currentWord) >= 0) { 
     result += currentWord + " "; 
     currentWord = ""; 
    } 
} 

console.log(result.trim()); // "banana candy cookie donught" 

Natürlich würden Sie verschiedenen Teil dieses, beispielsweise zu modifizieren, Verwenden Sie einen Satz für das Wörterbuch und berücksichtigen Sie die case [in] sensitivity.