«Реализация оптимального поиска дублирующих данных в операционной системе»

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

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

Поиск информации (данных) представляет собой процесс выявления в некотором множестве документов (текстов) всех таких, которые посвящены указанной теме (предмету), удовлетворяют заранее определенному условию поиска (запросу) или содержат необходимые (соответствующие информационной потребности) факты, сведения, данные.

Дублирующие данные это данные одинаковые либо по названию, либо по содержанию, по типу , по дате создания, по размеру.

Работа поисковой системы происходит в три этапа. Из которых два первых являются подготовительными и незаметны для пользователя. Сначала поисковый указатель собирает информацию. Затем, если поиск, к примеру ведется в Интернете, поисковик копирует заданную Web страницу на сервер поискового указателя, просматривает ее, находит все гиперссылки которые на ней имеются.

После копирования розыcкиваемых Web-ресурсов на сервер поисковой системы начинается второй этап работы — индексация. В ходе индексации создаются специальные базы данных, с помощью которых можно установить, где и когда в Интернете встречалось, то или иное слово. Считается, что индексированная база данных — это своего рода словарь. Она необходима для того, чтобы поисковая система могла очень быстро отвечать на запросы пользователей. Современные системы способны выдавать ответы за доли секунды, но если не подготовить индексы заранее, то обработка одного запроса будет продолжаться часами.

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

В работе многих поисковиков есть серьёзные недостатки:

1. поиск по ключевым словам даёт слишком много ссылок и многие из них бесполезны.

2. огромное количество поисковых машин с разными пользовательскими интерфейсами порождает проблему когнитивной перегрузки.

3. методы индексирования баз данных, как правило, не связаны с информационным содержанием.

4. часто выдаются ссылки на информацию, которой уже давно нет.

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

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

Оптимизация поможет организовать мгновенный доступ к документам, электронной почте, программам, приложениям и файлам мультимедиа. Автоматически и логически упорядочить файлы и папки поиска.

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

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

Целью дипломной работы является реализация алгоритма поиска данных.

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

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

Объем и структура работы

Дипломная работа состоит из введения, теоретической части, программной реализации «The Disk Explorer in Computer(TDEIC)» и из руководства пользования программным продуктом («The Disk Explorer in Computer(TDEIC)»).

Во введении объясняется актуальность данной разработки, указываются цели и задачи данной работы.

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

Во второй части приводится программная реализация и описание основных блоков программы.

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

Заключение содержит основные результаты и выводы по дипломной работе.

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

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

1.2. Понятие информации, накопители и носители информации

В тот самый момент, когда первый компьютер впервые обработал несколько байт данных моментально встал вопрос: где и как хранить полученные результаты? Как сохранять результаты вычислений, текстовые и графические образы, произвольные наборы данных?

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

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

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

– человек мог спутать различные данные;

– неправильно понять другого человека;

– элементарно забыть что-то важное;

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

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

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

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

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

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

1. Устройство чтения перфокарт: предназначено для хранения программ и наборов данных с помощью перфокарт – картонных карточек с пробитыми в определенной последовательности отверстиями. Перфокарты были изобретены задолго до появления компьютера, с их помощью на ткацких станках получали очень сложные и красивые ткани, потому что они управляли работой механизма. Изменишь набор перфокарт и рисунок ткани будет совсем другим – это зависит от расположения отверстий на карте. Применительно к компьютерам был использован тот же принцип, только вместо рисунка ткани отверстия задавали команды компьютеру или наборы данных. Такой способ хранения информации не лишен недостатков: – очень низкая скорость доступа к информации;

– большой объем перфокарт для хранения небольшого количества информации;

– низкая надежность хранения информации;

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

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

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

С другой стороны стриммер пригоден только для накопления, хранения больших массивов информации, резервирования данных. Обрабатывать информацию с помощью стриммера практически невозможно – стриммер устройство последовательного доступа к данным: чтобы получить 5-й файл мы должны промотать четыре. А если нужен 7529-й ?

3. Накопитель на гибких магнитных дисках (НГМД – дисковод): сравнительное новое устройство хранения информации. Это устройство использует в качестве носителя информации гибкие магнитные диски – дискеты, которые могут быть 5-ти или 3-х дюймовыми. Дискета – это магнитный диск вроде пластинки, помещенный в картонный конверт. В зависимости от размера дискеты изменяется ее емкость в байтах. Если на стандартную дискету размером 5’25 дюйма помещается до 720 Кбайт информации, то на дискету 3’5 дюйма уже 1,44 Мбайта. Дискеты универсальны, подходят на любой компьютер того же класса оснащенный дисководом, могут служить для хранения, накопления, распространения и обработки информации. Дисковод – устройство параллельного доступа, поэтому все файлы одинаково легко доступны. Сейчас дискеты применяются в основном для резервирования небольших объемов данных и для распространения информации. Дискеты размером 5’25 дюйма морально устарели и используются редко.

К недостаткам относятся маленькая емкость, что делает практически невозможным долгосрочное хранение больших объемов информации, и не очень высокая надежность самих дискет.

4. Накопитель на жестком магнитном диске (НЖМД – винчестер): является логическим продолжением развития технологии магнитного хранения информации. Появились несколько лет назад и уже завоевали огромную популярность благодаря своим многочисленным достоинствам:

– чрезвычайно большая емкость;

– простота и надежность использования;

– возможность обращаться к тысячам файлов одновременно;

– высокая скорость доступа к данным.

Из недостатков можно выделить лишь отсутствие съемных носителей информации, все данные записаны внутри винчестера на жестких магнитных дисках. (В настоящее время используются внешние винчестеры и системы резервного копирования с дисками по типу дискет). Емкости современных винчестеров поистине устрашающи: еще пять лет назад винчестер емкостью 100 Мбайт казался недостижимым идеалом, пределом заветных мечтаний – казалось, что и половины его пространства хватит на много лет работы. Но прошло пять лет, и такие винчестеры уже даже не выпускаются как морально устаревшие. Им на смену пришли новые, более быстрые, более вместительные аппараты. Винчестеры емкостью 850 Мб, 1.6, 2.1, 3.5, 4.3 Гигабайт давно ни кого не удивляют. А ведь существуют винчестеры в 1000 раз более емкие – речь идет о Терабайтах информации. Одного такого винчестера хватило бы чтобы записать всю историю Древнего Мира.

Пока они используются только в очень солидных организациях.

5. Устройство чтения компакт-дисков (CD-ROM): появились несколько лет назад и уже широко распространились. В этих устройствах используется принцип считывания сфокусированным лазерным лучом бороздок на металлизированном несущем слое компакт-диска. Этот принцип позволяет достичь высокой плотности записи информации, а следовательно и большой емкости при минимальных размерах. Компакт-диск является идеальным средством хранения информации – дешевый, практически не подвержен каким-либо влияниям среды, информация записанная на нем не исказится и не сотрется, пока диск не будет уничтожен физически, имеет емкость 650 Мбайт, сравнимую с неплохим винчестером при этом его производство несравнимо дешевле и проще, при размерах с 5-ти дюймовую дискету вмещает информации в 900 раз больше, чем дискета.

Имеет только один недостаток – на компакт-диск нельзя записывать информацию. Данные на него записываются либо в процессе производства, либо потом, пользователем (устройство CD-R), но только единожды.[2]

6. Другие устройства накопления и хранения информации: кроме вышеперечисленных основных устройств накопления и хранения информации существуют некоторые другие, по разным причинам менее популярные. К таким устройствам относятся:

– магнитооптические диски;

– бернулли-диски;

– устройства резервирования данных;

– некоторые другие устройства.

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

1.3. Понятие файловой системы.

1.3.1. Определение файловой системы.

Файл (по английски File) - папка,скоросшиватель.

Файл - это поименованная область памяти на каком-либо физическом

носителе, предназначенная для хранения информации.

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

Файловая система (file system) – функциональная часть операционной системы, которая отвечает за обмен данными с внешними запоминающими устройствами.

1.3.2. Файловая система FAT.

Операционными системами Windows используется, разработанная еще для DOS файловая система FAT, в которой для каждого раздела и тома DOS имеется загрузочный сектор, а каждый раздел DOS содержит две копии таблицы размещения файлов (file allocation table – FAT).

FAT представляет собой матрицу, которая устанавливает соотношение между файлами и папками раздела и их физическим местоположением на жестком диске.

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

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

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

Элементы таблицы FAT представляют собой 12-, 16- и 32-битовые шестнадцатьричные числа, размер которых определяется программой FDISK, а значение непосредственно создается программой FORMAT.

Все гибкие диски, а также жесткие диски размером до 16 Мбайт используют в FAT 12-битовые элементы. Жесткие и съемные диски, имеющие размер от 16 Мбайт и более, обычно используют 16-битовые элементы.

Файловая система FAT использовалась во всех версиях MS-DOS и в первых двух выпусках OS/2 (версии 1.0 и 1.1). Каждый логический том имел собственный FAT, который выполнял две функции: содержал информацию распределения для каждого файла в томе в форме списка связей модулей распределения (кластеров) и указывал, какие модули распределения свободны.

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

В процессе выполнения работы были выявлены основные проблемы, связанные с реализацией поиска:

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

2. В полученных данных после индексации имеются данные которые дублируются. Необходимо выявить их.

Также были выявлены вопросы связанные с решением проблемы выявления дублирующих данных

Объект исследования: Дисковое пространство

Объект слежения: файлы

Цель: выявление дублирующих данных

Конечный результат: корректное удаление

Методы реализующие нахождение дублирующих данных: поиск, сортировка, семантический анализ, по элементное сравнение

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

Разработано программное приложение, реализующие предложенные в дипломе методы нахождения дублирующих данных.

9. h**t://ru.wikipedia.org

10. w*w.osys.r*

11. Кричевский, Р.Е. Сжатие и поиск информации. - М.: Радио и связь, 1989.

12. Митчелл К. Керман. Программирование и отладка в Delphi. М.:Вильямс.-2004.-589 с.

13. Фаронов В.В. Руководство программиста. –М.: «Нолидж», 2001.–880 с., ил.

14. Роман Кулаченко. Слежение за процессами и файлами в режиме пользователя. h**t://w*w.citforum.r*/programming/delphi/user-mode/

15. П. В. Шуманов, В.В. Фролов. Delphi 5 руководство разработчика баз данных