Как наиболее рационально подойти к разбиению очень большого текста на отдельные слова?

Всем здравствуйте!

Задумал написать на Визуальном бейсике программу, которая будет обрабатывать большие (ну очень большие!) тексты, разбивая их на отдельные слова. На ум приходит только такой подход к решению этой задачи:

1. В цикле проходим по всем словам текста, отправляя каждое из них во вложенный цикл.
2. Во вложенном цикле создаём 2 связанных между собой массива - массив (базу данных) всех найденных слов и массив счётчиков количества повторений для каждого слова.

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

Ахиллесова пята здесь это поиск слов в составляемой базе данных. На это уйдёт львиная часть времени.
Отсюда вопрос: можно ли как-нибудь оптимизировать этот процесс?
Мне на ум приходит, что можно попробовать вставлять в "базу данных" новые слова сразу в алфавитном порядке, а потом начинать поиск (но как?) с первой буквы слова-кандидата.

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

Пытался гуглить "VB6 разбить текст на отдельные слова", но там все ответы либо на VB.Net, либо вообще на других языках.

0

Используй либо коллекцию (которая хранит ключи упорядоченно), либо хеш таблицу Dictionary.

1

Сообщение от The trick Используй либо коллекцию (которая хранит ключи упорядоченно), либо хеш таблицу Dictionary.

Ну и скорость у вас!
Я даже не успел перечитать свой пост (для проверки), а ответ уже тут как тут!

Но всё-таки хотелось бы как-нибудь поподробнее

Про "хеш таблицу Dictionary" я вообще слышу первый раз в жизни, а вот с коллекцией... ну да, это интересный подход. А как добиться того, чтобы коллекция хранила ключи упорядоченно?
И ещё мне кажется, что массивы всё-таки работают быстрее чем коллекции, поскольку они не являются объектами, или нет?

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

Добавлено через 7 минут
Это я к тому, что исходный текст огромный-преогромный!

0

Сообщение от Power_Basic А как добиться того, чтобы коллекция хранила ключи упорядоченно?

Она и хранит их упорядоченно. Выставляй в качестве ключа слово, а в качестве значения - счетчик. Коллекция - это красно-черное дерево.

Сообщение от Power_Basic И ещё мне кажется, что массивы всё-таки работают быстрее чем коллекции, поскольку они не являются объектами, или нет?

А для чего тебе массивы? Тебе же нужен быстрый доступ по ключу.

Сообщение от Power_Basic Про "хеш таблицу Dictionary" я вообще слышу первый раз в жизни

Project->References->Microsoft Scripting Runtime. Обычно как раз словарь и используют для быстрого доступа по ключу.

1

Сообщение от The trick Она и хранит их упорядоченно. Выставляй в качестве ключа слово, а в качестве значения - счетчик. Коллекция - это красно-черное дерево.

Честно говоря, я сначала подумал, что это какое-то "поэтическое" сравнение, которое вроде бы совсем не вяжется с тематекой форума
Но на всякий случай погуглил и, к своему удивлению, выяснил, что это "деревья поиска", ну и там вообще целая наука

Сообщение от The trick А для чего тебе массивы? Тебе же нужен быстрый доступ по ключу.

Ну в принципе, да.

Сообщение от The trick Project->References->Microsoft Scripting Runtime. Обычно как раз словарь и используют для быстрого доступа по ключу.

Спасибо, попробую разобраться.

А ещё вот такой вопрос. Может быть имеет смысл создать сразу несколько коллекций, - по одной на каждую букву? Это вроде бы должно существенно сократить время поиска. Ну а потом (уже в самом конце) их все объединить в одну общую и распечать в файл.

0

Сообщение от Power_Basic А ещё вот такой вопрос. Может быть имеет смысл создать сразу несколько коллекций, - по одной на каждую букву? Это вроде бы должно существенно сократить время поиска. Ну а потом (уже в самом конце) их все объединить в одну общую и распечать в файл.

Не стоит.

1

Сообщение от Power_Basic 2. Во вложенном цикле создаём 2 связанных между собой массива - массив (базу данных) всех найденных слов и массив счётчиков количества повторений для каждого слова.

Лучше один массив структур.

Сообщение от Power_Basic Ахиллесова пята здесь это поиск слов в составляемой базе данных. На это уйдёт львиная часть времени. Отсюда вопрос: можно ли как-нибудь оптимизировать этот процесс?

Как вариант ассоциативный массив основанный на красно-чёрном дереве или похожем алгоритме.

Сообщение от Power_Basic Мне на ум приходит, что можно попробовать вставлять в "базу данных" новые слова сразу в алфавитном порядке, а потом начинать поиск (но как?) с первой буквы слова-кандидата.

Можете создать массив букв с которых начинаются слова а в нем массив слов (массив массивов). Тогда быстрее будет поиск т. к. потребуется искать только в части слов (начинающихся с той же буквы) а не среди всех.

1

Сообщение от The trick Не стоит.

Спасибо, понял.

Сообщение от locm Сообщение от Power_Basic 2. Во вложенном цикле создаём 2 связанных между собой массива - массив (базу данных) всех найденных слов и массив счётчиков количества повторений для каждого слова. Лучше один массив структур.

Ну да, пожалуй так оно логичнее, да и поаккуратнее будет выглядеть общий код относительно кода с двумя отдельными связанными массивами.

Наверно только на практике можно будет выяснить, что работает быстрее - коллекция или массив.

Сообщение от locm Как вариант ассоциативный массив основанный на красно-чёрном дереве или похожем алгоритме.

Ну нет, нырять в такие глубины теории прямо сейчас я точно не готов

Сообщение от locm Можете создать массив букв с которых начинаются слова а в нем массив слов (массив массивов). Тогда быстрее будет поиск т. к. потребуется искать только в части слов (начинающихся с той же буквы) а не среди всех.

Тоже интересный вариант. Что-то вроде картотеки
Пожалуй, при таком подходе удобнее будет работать, чем, как я изначально задумывал, создавать много (для каждой буквы) самостоятельных массивов.

Но всё-таки сейчас начну с коллекций, потому что хотя бы просто хочется попробовать, насколько они могут конкурировать в скорости с массивами. И если выигрыш в скорости будет невелик, тогда, да, вернусь к варианту с "картотекой"

0

Такая дискуссия, будто счет будет идти на многие миллионы!
Всего английских слов около полмиллиона. Из них компьютерной тематики сколько наберётся?
Я как то делал программу, которая собирала словарный запас скажем Толстого, и на его основе генерировала свои тексты.
Сборка словаря, а это такая штука, где каждому слову соответствует своя пара. например слово очень используется со словами:
очень = раздражать,|близко|приближающегося|удобн ая
в свою очередь близко
близко = к|от
ну и так далее.
В общем такой словарь создаётся скажем из "Войны и мир" минут за 4-5. в MAP. А потом новый текст создаётся уже за секунду из готовой map.
Т.е. доступ в таком объёме слов комп делает мгновенно. Слов то не чисел, существует в мире на так много...

0

Сообщение от Power_Basic Ну нет, нырять в такие глубины теории прямо сейчас я точно не готов

Коллекция как раз и является ассоциативным массивом основанном на красно-черном дереве.

Сообщение от Power_Basic что работает быстрее - коллекция или массив.

Обычный массив тут вообще не нужен.

0

Сообщение от Pro_grammer Такая дискуссия, будто счет будет идти на многие миллионы!

Боюсь что именно многие миллионы

Сообщение от Pro_grammer Всего английских слов около полмиллиона. Из них компьютерной тематики сколько наберётся?

Иллюзия!
Ну да, навскидку-то именно так оно и выглядит.

Как сказал сатирик про великий и могучий русский мат, "Слов мало, слов всего пяток, зато какие комбинации!"

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

Ну вот самые длинные термины из упомянутой выше книги:

ConvertSecurityDescriptorToStringSecurit yDescriptor ConvertStringSecurityDescriptorToSecurit yDescriptor MmAllocateContiguousMemorySpecityCacheNo de KiDynamicHeteroCpuPolicyImportantPriorit y PoFxIssueComponentPerfStateChangeMultipl e KiDynamicHeteroCpuPolicyImportantShort SystemCombinePhysicalMemoryInformation IoPagingWriteLowPriorityBumpedCount ScPerformPageCombiinennervicelmages CLLSDDAppCicationActivttionMtntgee IoPagingReadLowPriorityBumpedCount JibOObectCpuRateeoiOroiloniorattio SetFileOmppeetimnNotificitinnMmdes KeRevertToUserGroupAffinityThread KiDynamicHeteroCpuPolicyImportant SepCachedHandlesEntryBnoIsolation

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

Сообщение от Pro_grammer Я как то делал программу, которая собирала словарный запас скажем Толстого, и на его основе генерировала свои тексты.

С Толстым проще
Как это ни смешно звучит, но у него словарный запас "беднее" чем, например, у библиотеки MSDN
Там же все многочисленные параметры будут восприниматься компьютером, как отдельные самостоятельные термины. А их там "склевают", как хотят, в любых сочетаниях.

Сообщение от Pro_grammer Слов то не чисел, существует в мире на так много...

Согласен, отдельных, "нормальных" слов не так уж и много

Сообщение от Pro_grammer Сборка словаря, а это такая штука, где каждому слову соответствует своя пара. например слово очень используется со словами: очень = раздражать,|близко|приближающегося|удобн ая в свою очередь близко близко = к|от ну и так далее.

На самом деле, мне сейчас тоже хочется сделать для себя такой словарь. Как выяснилось, OCR и с русскими словами тоже иногда косячит.

Сообщение от The trick Коллекция как раз и является ассоциативным массивом основанном на красно-черном дереве.

Я вчера немного почитал про коллекции и вспомнил, почему я отказался от них ещё с самого начала. Они же на Вариантах построены, а их все ругают за относительную медлительность и относительную прожорливость в отношении памяти.
Но с ними, да, удобнее работать чем с массивами, и я обязательно устрою между ними "соревнование"

А вот такой ещё вопрос.
Вот допустим, уже у меня готова отсортированная коллекция. Как мне её сбросить на диск в виде текстового файла?
С массивом это легко, а здесь как?

Сообщение от The trick Сообщение от Power_Basic что работает быстрее - коллекция или массив. Обычный массив тут вообще не нужен.

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

Сообщение от locm Можете создать массив букв с которых начинаются слова а в нем массив слов (массив массивов). Тогда быстрее будет поиск т. к. потребуется искать только в части слов (начинающихся с той же буквы) а не среди всех.

Я немного поразмышлял на эту тему. Получается, что "внешний" массив будет содержать "внутренние" массивы тоже в виде Вариантов, да? А как это повлияет на общую скорость?

Сообщение от Power_Basic Сообщение от locm Лучше один массив структур. Ну да, пожалуй так оно логичнее, да и поаккуратнее будет выглядеть общий код относительно кода с двумя отдельными связанными массивами.

Нет, всё-таки я вспомнил, почему с самого начала отказался от структур. Там же нельзя использовать динамические строки и надо уже с самого начала объявлять размер каждой строки. А какой размер мне выбрать?
Вот самое длинное слово из процитированных выше состоит из 51 буквы. А есть же очень много коротких слов. Но и для них тогда тоже придётся резервировать столько же байтов памяти. А словарик-то не маленький

0

Сообщение от Power_Basic Я вчера немного почитал про коллекции и вспомнил, почему я отказался от них ещё с самого начала. Они же на Вариантах построены, а их все ругают за относительную медлительность и относительную прожорливость в отношении памяти.

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

Сообщение от Power_Basic Вот допустим, уже у меня готова отсортированная коллекция. Как мне её сбросить на диск в виде текстового файла? С массивом это легко, а здесь как?

Проходишь по коллекции и сохраняешь пары ключ значение. Формат VB6 коллекции описан тут.

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

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

Сообщение от Power_Basic Я немного поразмышлял на эту тему. Получается, что "внешний" массив будет содержать "внутренние" массивы тоже в виде Вариантов, да? А как это повлияет на общую скорость?

Ну это тоже самое дерево. Только зачем останавливаться на одном уровне? В плане потребления памяти это конечно не очень эффективно, зато в скорости доступа очень быстро.

Сообщение от Power_Basic Нет, всё-таки я вспомнил, почему с самого начала отказался от структур. Там же нельзя использовать динамические строки и надо уже с самого начала объявлять размер каждой строки. А какой размер мне выбрать? Вот самое длинное слово из процитированных выше состоит из 51 буквы. А есть же очень много коротких слов. Но и для них тогда тоже придётся резервировать столько же байтов памяти. А словарик-то не маленький

Почему нельзя использовать динамические строки? Можно.

1

Сообщение от Power_Basic Боюсь что именно многие миллионы

Тогда нужно хорошо подумать над требуемым объемом памяти. Если допустим будет 10 миллионов слов со средней длиной 20 символов это потребует 200 МБ в случае 1 байт на символ и без учета накладных расходов. В реальности требуемый объем памяти может превысить 2 ГБ, что больше допустимого для x86 процесса и стоит задуматься о создании x64 приложения. В компе должно быть достаточно памяти.

Сообщение от Power_Basic Вот допустим, уже у меня готова отсортированная коллекция.

Возможно ее не получится отсортировать, т. к. построена на основе дерева, а не списка или массива.

Сообщение от Power_Basic действительно ли коллекции намного медлительнее чем массивы или нет.

Это зависит от задачи. В данном случае массив вероятнее будет более медленным.

Сообщение от Power_Basic Я немного поразмышлял на эту тему. Получается, что "внешний" массив будет содержать "внутренние" массивы тоже в виде Вариантов, да?

Это зависит от формата массива массивов в VB. По нормальному должны быть конкретные типы, а не вариант.

0

Сообщение от Power_Basic ConvertSecurityDescriptorToStringSecurit yDescriptor

Ну да, согласен, тем более, что ещё и так:

ConvertSecurityDescriptorToStringSecurit yDescriptorA
ConvertSecurityDescriptorToStringSecurit yDescriptorW

Но всё равно, я не понимаю, когда и в чем может помочь список всех этих слов? Для проверки правописания всё же более пригодно разбить их на составляющие + алгоритмы нечеткого поиска?

Вспоминаю, что у меня где то была MSDN для VS 6 версии, на 2-х вроде CD дисках, до всеобщего Интернета её на дисках распространяли. Там наверняка большая часть таких слов есть и написана правильно.

2

Сообщение от The trick На текущей задаче это практически не будет иметь значения. Для программы которая отработает 1 раз (парсинг текста) это неважно.

Ну всё-таки не один раз. Предполагается, что я буду время от времени подкидывать в эту "мясорубку" всё новые и новые тексты. Накопленная база слов будет неуклонно расти, и поиск по ней будет отнимать у процессора всё больше и больше времени.

Сообщение от The trick Проходишь по коллекции и сохраняешь пары ключ значение. Формат VB6 коллекции описан тут.

Спасибо, попробую разобраться.

Сообщение от The trick Ну это тоже самое дерево. Только зачем останавливаться на одном уровне? В плане потребления памяти это конечно не очень эффективно, зато в скорости доступа очень быстро.

Но память же тоже имеет важное значение. Из своих восьми гигов я могу использовать только три.

Вы недавно говорили, что объём доступной памяти можно как-то расширить с помощью WINAPI. Я тогда не особо вникал, потому что не было практической необходимости. Там не слишком сложно для продвинутой домохозяйки?

Сообщение от The trick Сообщение от Power_Basic Нет, всё-таки я вспомнил, почему с самого начала отказался от структур. Там же нельзя использовать динамические строки и надо уже с самого начала объявлять размер каждой строки. Почему нельзя использовать динамические строки? Можно.

Ну тогда это существенное преимущество Визуального бейсика перед PowerBasic'ом, в котором такое невозможно:

PowerBASIC's User-Defined Type is similar to a C struct or Pascal record. The elements of a User-Defined Type may include any of PowerBASIC's data types, with the exception of dynamic (variable-length) strings, field strings, and arrays of dynamic strings.

0

Сообщение от Power_Basic Ну всё-таки не один раз. Предполагается, что я буду время от времени подкидывать в эту "мясорубку" всё новые и новые тексты. Накопленная база слов будет неуклонно расти, и поиск по ней будет отнимать у процессора всё больше и больше времени.

Это не имеет значения. Разбор 1000000 слов и разбор 1000020 слов, по времени будет практически идентичен.

Сообщение от Power_Basic Но память же тоже имеет важное значение. Из своих восьми гигов я могу использовать только три.

Ну тут компромисс, либо скорость, либо память. Самый оптимальный вариант в этом случае - хеш таблица.

Сообщение от Power_Basic Вы недавно говорили, что объём доступной памяти можно как-то расширить с помощью WINAPI. Я тогда не особо вникал, потому что не было практической необходимости. Там не слишком сложно для продвинутой домохозяйки?

Да много как можно сделать. Только для текущей задачи это не имеет значения - объемы данных не те.

0

Сообщение от locm Тогда нужно хорошо подумать над требуемым объемом памяти. Если допустим будет 10 миллионов слов со средней длиной 20 символов это потребует 200 МБ в случае 1 байт на символ и без учета накладных расходов. В реальности требуемый объем памяти может превысить 2 ГБ, что больше допустимого для x86 процесса и стоит задуматься о создании x64 приложения. В компе должно быть достаточно памяти.

К сожалению, создание x64 приложений мне пока не по зубам, а словарь нужен уже прямо сегодня, а лучше бы даже ещё вчера

Сообщение от locm Сообщение от Power_Basic Вот допустим, уже у меня готова отсортированная коллекция. Возможно ее не получится отсортировать, т. к. построена на основе дерева, а не списка или массива.

Вот это сюрприз!
А как же тогда слова-то по алфавиту расставить в самом концу?

Сообщение от locm Сообщение от Power_Basic действительно ли коллекции намного медлительнее чем массивы или нет. Это зависит от задачи. В данном случае массив вероятнее будет более медленным.

Это вы сейчас сравниваете поиск по ключу в коллекции с проходом массива обычным циклом FOR... NEXT?

Сообщение от locm Сообщение от Power_Basic Я немного поразмышлял на эту тему. Получается, что "внешний" массив будет содержать "внутренние" массивы тоже в виде Вариантов, да? Это зависит от формата массива массивов в VB. По нормальному должны быть конкретные типы, а не вариант.

Ну значит придётся мне снова у The trick'а консультироваться
Как я понял, он здесь главный специалист по VB.

0

Power_Basic, посмотри эту простейшую реализацию хеш-таблицы.

1

Сообщение от Pro_grammer Но всё равно, я не понимаю, когда и в чем может помочь список всех этих слов? Для проверки правописания всё же более пригодно разбить их на составляющие + алгоритмы нечеткого поиска?

Ну вот на составляющие-то и буду по словарю разбивать
И даже уже придумал приблизительный алгоритм, как именно это будет происходить
А если какое-то "склеенное" слово, заложенное в словарь, встретится целиком в распознаваемом тексте, ну тогда даже ещё лучше. Есть неплохой шанс, что OCR, опираясь на пользовательский словарь, правильно его распознает, и дальнейшие пляски с бубном вокруг этого сложного слова уже не потребуются.

Сообщение от Pro_grammer Вспоминаю, что у меня где то была MSDN для VS 6 версии, на 2-х вроде CD дисках, до всеобщего Интернета её на дисках распространяли. Там наверняка большая часть таких слов есть и написана правильно.

Во, спасибо за идею!
У меня она тоже есть (полтора гига на диске занимает). Вот её-то родимую и буду парсить
А то ведь я уже собирался скачивать WGET'ом всю современную
Ну или хотя бы ту ёё часть, которая уместится на всех моих носителях

0

Сообщение от Power_Basic Вот её-то родимую и буду парсит

Используй dumpbin и просто перечисляй все экспортированные функции из нужных либ.

0