проблема с массивом

[vlad7]

проблема с массивом

Может кто-нибудь подскажет?
Есть такая задача:
С диска считывается в память массив байтов, цепочки из которых упорядочены по законам естественного языка. Каждая цепочка, в свою очередь, тоже упорядочена по законам того же самого естественного языка. В исходной 33-ричной системе исчисления при общей длине массива более миллиона байтов время нахождения частоты повторения каждой исходной цепочки в считываемой кипе байтов начинает расти с невероятной быстротой (предположительно по геометрической прогрессии, где знаменатель прогрессии - это кол-во шагов, необходимых для определения частоты повторения цепочки при условии, что в исходном массиве таких цепочек две, а члены прогрессии - это просто-напросто ряд натуральных чисел - считываемые цепочки байт). Подскажите, не поможет ли мне перевод из 33-ричной с-мы в двоичную, или может, кто-нибудь сталкивался с подобной задачей и натолкнет меня на правильный путь? Хочется приемлемых временных результатов хотя бы с десятком миллионов байт. Может проблема в аглоритме, и если да, то как мне выбрать нужный алгоритм и какими методами мне его оценить? Спасибо

 

[balkauser]

А можно изложить проблему с помощью того самого "естественного языка", с учётом того, что никто кроме Вас не знает специфику задачи. Что такое "цепочка"? Что значит "цепочки из которых упорядочены по законам естественного языка"? Что значит "Каждая цепочка упорядочена по законам естественного языка"?

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

Из этого потока сознания мало что ясно, но возможно префиксное дерево спасёт отца русской революции.

 

[vlad7]

Спасибо за ссылку, но в задачу пока не входит поиск и сортировка, к сожалению.

 

[Ferox]

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

P.S. А сортировку делать надо обязательно. И строить индекс в виде хотя бы бинарного дерева тоже. Только я затрудняюсь сказать, в каком виде наиболее разумно представлять данные, для сортировки и индексирования. Вот это как раз должны знать дорвейщики и разработчики ПС.

P.P.S. Насколько мне известно, самые хилые дорвейщики индексируют трехсловники. Но я не уверен, насколько это правильно с общеметодической точки зрения.

 

[balkauser]

Спасибо за ссылку, но в задачу пока не входит поиск и сортировка, к сожалению.

Я думал, что нахождение частоты это по сути то же самое, что поиск. Вероятно я не прав. Тогда поясните нормальным языком, в чём суть задачи.

 

[vlad7]

Я извиняюсь, что так непонятно написал. Думал так будет для программистов понятнее.
Что значит "цепочки из которых упорядочены по законам естественного языка"? - Это предложение из слов. Что значит "Каждая цепочка упорядочена по законам естественного языка"? - Это слово
Нахождение частоты повторения каждой исходной цепочки - это сколько раз слово повторяется в массиве. Т.е., конечно, можно связать с поиском, но по-моему поиск здесь не главное, так как нужно определить частоту всех слов

 

[Тыемураз]

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

 

[vlad7]

Да, исходные данные - текстовый файл

 

[balkauser]

Я, наверное, совсем тупой, но мне до сих пор не ясно, что же именно нужно. Понятно, что есть текст и от него нужна какая-то статистика, непонятно какая. Нужно найти частоту всех слов, встречающихся в тексте? Есть некий эталонный набор слов или словосочетаний, частоту которых нужно найти в тексте? Свой вариант?

Как я уже писал

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

 

[vlad7]

Есть некий эталонный набор слов или словосочетаний, частоту которых нужно найти в тексте?

Да, каждое слово - это в своем роде "эталонный набор" байтов

 

[balkauser]

Да, каждое слово - это в своем роде "эталонный набор" байтов

Видимо, Вам безумно лень всё таки написать полное, однозначное и понятное описание решаемой задачи. И при этом Вы всё ещё рассчитываете на помощь .

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

 

[vlad7]

Видимо, Вам безумно лень всё таки написать полное, однозначное и понятное описание решаемой задачи. И при этом Вы всё ещё рассчитываете на помощь .

Пока исходя из ответов создаётся впечатление, что есть текст и набор слов. Нужно узнать частоту упоминания слов в тексте.

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

С памятью проблем пока нет. Проблема - время.

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

 

[balkauser]

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

Тогда, где проблема? Какое быстродействие Вам нужно?

Наивная реализация, сделанная мной минут за 20, менее, чем за 1 секунду работы, говорит, что "Анна Каренина" (примерно 1.7 MB текста) содержит около 270 тысяч слов из них разных около 34 тысяч (словоформы - разные слова) и десятка лидеров по частоте такая:
и - 12914
не - 6538
что - 6141
в - 5722
он - 5552
на - 3594
она - 3433
с - 3358
я - 3217
как - 2686

Более 19 тысяч слов упоминаются ровно один раз (понятное дело, только потому, что словоформы - разные слова).

 

[vlad7]

Ну, да. Тока у меня еще все матюки убирает (стоп-слова), частота слов определяется в чистом тексте

Правда, реализация, наверное, ужасная, слова, как объекты со своими характеристиками в векторе висят. 1МБ - где-то мин 5 лопатит

Проблема, что все характеристики - это не только частота (еще и стемминг должен быть) нужно хранить, доступ через методы класса - все так начинает тормозить после 1 МБ - хочу про оценочные методы алгоритмов почитать, может подскажете книгу?

Поубирал методы доступа к закрытым членам, сделал их открытыми, обращаюсь напрямую - скорость - в два раза поднялась. Ото дела.

 

[Klez]

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

 

[vlad7]

Спасибо за Хештейбл. Она мне и в поиске потом поможет, если понадобится, ведь так?

 

[Губитель]

Всем привет.Пастух поехал посещать пирамиды Гиза и Кукулкана,меня попросил поддержать данную тему,хотя я не нашел автора Валико,но догадываюсь,что это именно это.
Разрешение подобного рода задач несет в себе ,не побоюсь сказать развитие прогресса в целом .И возможно будет рождаться чудо на глазах,если мы воспользовавшись групповым потоком сознания,не упустим главного.
Я также как и вы имею дольку разделения левого и правого,соответственно вижу решение оптимизации процесса в двух направлениях :
1.внести логику предугадывания некоторых проходов
2.если рассматривать теорию 33 разрядной системы,то следует вспомнить,что двоичная система определена как единица величины електрического потенциала
"да" и "нет".По идее 33 разрядную систему можно использовать как абстракцию некоторого фона-изображения в 33 цвета.
То есть в итоговой состовляющей некоторое предложение или раздел предложений будет выливаться в некоторую картинк с разхличными оттенками.
Еще издавна человечество уже пользуется некоторыми технологиями такой компоновки ,пользуясь словами-жучками,позволяющими прследить движенение некоторого индивидума-носителя или же более сложные формы такой технологии,позволяющей компоновать целые предложения и формировать в зависимости от изменяемого оттенка ,некоторый характер движения носителя.

 

[vlad7]

Губитель - по-моему вы Тыемураз

 

[Губитель]

Губитель - по-моему вы Тыемураз

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

 

[vlad7]

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

Я понимаю, вы это про автоматизированный ввод капчи - что есть собственно огромный шаг вперед в прогрессе компьютерной науки