Добавить пробелы между словами в без пробелов

Question

Я на OS X, и в target-c я пытаюсь преобразовать

, например, "Bobateagreenapple"

в "Боб съел зеленое яблоко"

Есть ли способ сделать это эффективно?Будет ли что-то с проверкой орфографии работать?

РЕДАКТИРОВАТЬ: Просто некоторая дополнительная информация: я пытаюсь создать что-то, что берет некоторый неформатированный текст (например, текстовая копия, вставленная из старых файлов PDF, которые заканчиваются без пробелов, особенно из интернет-архивов, таких как JSTOR).Поскольку неверно отформатированный текст, вероятно, будет длинным ... ну, я просто пытаюсь выяснить, возможно ли это, прежде чем я на самом деле пытаюсь действительно написать систему, только чтобы выяснить, что для исправления абзаца текста требуется 2 часа.

Answer 1

Одной из возможностей, которую я опишу не для ОС, является поиск всех возможных слов, составляющих набор букв.

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

Псевдокод будет выглядеть примерно так:

FindWords(vector<Sentence> sentences, Sentence s, Word w, Letters l)
{
    if (l.empty() and w.empty())
        add s to sentences;
        return;
    if (l.empty())
        return;
    add first letter from l to w;
    if w in dictionary
    {
        add w to s;
        FindWords(sentences, s, empty word, l)
        remove w from s
    }
    FindWords(sentences, s, w, l)
    put last letter from w back onto l
}

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

Answer 2

Решение этой проблемы намного сложнее, чем что-либо, что вы найдете в фреймворке. Обратите внимание, что даже в вашем примере есть другие «решения»: «Боб чай зеленого яблока», для одного.

Очень наивным (и не очень функциональным) подходом может быть использование средства проверки орфографии, чтобы попытаться выделить одно «настоящее слово» за раз в строке; конечно, в этом примере это будет работать только потому, что «Боб» - это английское слово.

Это не означает, что нет способа выполнить то, что вы хотите, но то, как вы формулируете этот вопрос, указывает мне, что это может быть намного сложнее, чем вы ожидаете. Может быть, кто-то может дать вам приемлемое решение, но держу пари, что им нужно будет знать гораздо больше о том, что именно вы пытаетесь сделать.

Редактировать: в ответ на ваши изменения, вероятно, потребуется меньше усилий, чтобы запустить какой-либо инструмент OCR для PDF и исправить его вывод, чем просто исправить то, что может дать вам эта система, не говоря уже о ее программировании *

Answer 3

Я реализовал решение, код доступен по проекту кода:

http://www.codeproject.com/Tips/704003/How-to-add-spaces-between-spaceless-strings

Моя идея состояла в том, чтобы расставить приоритеты по результатам, которые используют большинство символов (предпочтительно все), а затем отдать предпочтение тем, у которых самые длинные слова, потому что слова длиной 2,3 или 4 символа часто могут случайно появляться из пропущенных символов. В большинстве случаев это дает правильное решение.

Чтобы найти все возможные перестановки, я использовал рекурсию. Код довольно быстрый даже с большими словарями (проверено с 50 000 слов).