Разделить строку на словарные слова и словарные слова

Question

Я хочу разбить строку на последовательность слов, используя словарь.

Следующая функция дает мне только слова с границами букв.

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

Я хочу разделить текст на словарные словарные и словарные слова.

Например:

Iamno123prisoner - Я не 123 заключенному

USAisveryrich - США очень богат

Albertgaveme5rupees - Альберт дал мне 5 рупий

Пример словаря c a Here для refrence.

Answer 1

Если словарь содержит много слов, вам потребуется более быстрое решение, чем сопоставление одного слова за раз подряд с подстроками входного текста. Если в словаре есть десять тысяч слов, вам необходимо провести не менее десяти тысяч комбинаций с этим наивным подходом.

Более эффективное решение включает использование trie, в котором вы сохранили слова слова. Проверка наличия слова в словаре требует только одного прохода через строку.

Другим преимуществом является то, что вы можете найти самое длинное совпадение, начиная с заданной позиции в тексте. Этот подход продемонстрирован в следующем фрагменте, который включает небольшой словарь, достаточный для обработки ваших примеров. Вы можете заменить это своим собственным словарем при локальном запуске кода.

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" 

Примечание результат будет содержать два пробела, если есть два последовательных слов из словаря. Вы можете исправить это с помощью регулярного выражения.

Это не самое прекрасное решение (вы можете сделать его рекурсивным, что может быть более читаемым), и оно не предоставляет несколько решений (см. Ссылку DP в комментарии для этого).

Редактировать это не учитывает слова, не содержащие словаря.

Используя простой жадный алгоритм:

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" 

Конечно, вы хотели бы изменить различные части этого, например, используйте набор для словаря и учитывайте чувствительность к случаю [in].