Обработка текстовой информации
Практическая работа №7. Редактирование текста
- Повторять определения текстового процессора и текстового документа;
- Выполнять самостоятельную работу;
- Изучать правила ввода текста;
- Редактировать текст;
- редактирование;
- вставка;
- замена;
- удаление.
Проверка домашнего задания
Возможности текстового процессора
- Текстовые процессоры позволяют создавать тексты, состоящие из букв, цифр, знаков препинания и специальных символов, которые можно ввести с помощью клавиатуры;
- позволяют включать в текст надписи, списки, таблицы, схемы, рисунки, фотографии, проверять орфографию.
Проверка домашнего задания
Что вы понимаете под текстовым документом?
Текстовый документ – это любой текст, созданный с помощью текстового редактора (процессора).
Проверка домашнего задания
С тас м атлак
Проверка домашнего задания
Какие правила необходимо соблюдать при наборе (вводе) текста?
1. Там, где это нужно, использовать прописные буквы. С тас М атлак
Проверка домашнего задания
2. Все знаки препинания, кроме тире, ставить сразу же за последней буквой слова, после любого знака препинания нажимать клавишу Пробел. Тире выделять пробелами с двух сторон.
Ошибку, допущенную при вводе текста, исправлять так:ошибочный символ, расположенный справа от курсора,удалять клавишей Delete,а слева от курсора–клавишей
Backspase.
Проверка домашнего задания
Ошибку, допущенную при вводе текста, исправлять так: ошибочный символ, расположенный справа от курсора, удалять клавишей Delete,а слева от курсора–клавишей Backspase.
Самостоятельная работа. Редактирование текста (повторение)
Шутка - утка.
У про100го 100рожа
Непро100рный дом:
Часто в нем 100ножка
Бродит под 100лом.
Дорожит 100ножка
Чи100тою ног
И 100личной ваксой
Чистит 100 сапог.
Соедините стрелками надписи с соответствующими им элементами рисунка (раб. тетрадь стр.71 № 28)
Поле ввода Строка заголовка Сворачивающая кнопка Закрывающая кнопка Строка меню
Название приложения
При вводе текста необходимо придерживаться следующих правил:
1. Там, где это нужно, использовать прописные буквы. 2. Все знаки препинания, кроме тире, ставить сразу же за последней буквой слова, после любого знака препинания нажимать клавишу Пробел. Тире выделять пробелами с двух сторон. 3. Ошибку, допущенную при вводе текста, исправлять так: ошибочный символ, расположенный справа от курсора, удалять клавишей Delete (делейт), а слева от курсора – клавишей Backspase (бакспейс). 4. При наборе текста на компьютере не следить за концом строки: как только он будет достигнут, курсор автоматически перейдет на начало следующей строки. 5. Для перехода к вводу нового абзаца (или строки стихотворения), нажимать клавишу Enter (энтер).
Читаем учебник на странице 90
Информатека
Информатка
Информатика
Инфарматика
Инфрматика
Информатика
Практическая работа №7. Редактирование текста
- Вставьте слог «на» в слова:
КАРЕЙКА, КАВА, KОMTA, КАТОХОДЕЦ, ЗНИЕ
- Удалите лишнюю букву
ВСЛАСТЬ, КРАСКА, СКЛОН, ПОЛК, ТЕПЛО, БЕДА, ЭКРАН
Практическая работа №7. Редактирование текста
Замени одну букву в слове, чтобы получилось:
- Название города: СОКИ, УХА, ТУЧА, БАКИ.
- Название реки: УПАЛ, ОСА, КАША, ВОЛНА.
- скоро у нас каникулы я поеду вместе с папой в сочи митя с братом поедут в город иркутск, на озеро байкал а таня будет отдыхать в деревне у тети зои эта деревня стоит на берегу оки у тети в доме живет кот мурзик
Редактирование текста
Отредактируйте так, чтобы каждая пословица занимала всего одну строку.
Шило в мешке не утаишь. Не все коту масленица.
Кончил дело, гуляй смело. Готовь сани летом, а телегу - зимой.
Пар кости не
Без труда не
выловишь рыбку из пруда.
золото, что блестит. Слово - серебро, молчанье - золото.
Раньше встанешь - раньше работу кончишь. Цыплят по осени
Делу - время, потехе - час. Сначала подумай,
потом начинай. Семь раз примерь,
один раз отрежь. Работа страшна не рукам,
а глазам.
боится. От добра
- Повторял(а) определения текстового процессора и текстового документа;
- Изучал(а) правила ввода текста;
- Редактировал(а) текст.
- §2.9 с.90
Технология обработки текстовой информации Prezentacii. com Подготовил презентацию: учитель информатики МОУ СОШ № 1 г. Можайска Московской обл. Шлямина Е. А.
Технология обработки текстовой информации 1. 2. 3. 4. 5. Создание и редактирование документов Форматы текстовых файлов Форматирование документа Гипертекст Компьютерные словари и системы машинного перевода текстов 6. Системы оптического распознания документов
Создание и редактирование документов Для обработки текстовой информации на компьютере используют приложения общего назначения – текстовые редакторы, которые позволяют создавать, редактировать, форматировать, сохранять и распечатывать текст
Текстовые редакторы Простые текстовые редакторы: простейшее форматирование шрифта (Windows Блокнот) Текстовые процессоры: вставка списков и таблиц, проверка орфографии и т. д. (Microsoft Word и Star. Office Writer) Настольные издательские системы: подготовка к изданию журналов и газет (Adobe Page. Maker)
Создание документа ü Создание документа начинается с выбора шаблона. ü Для создания документов со сложной структурой используют Мастера ü В процессе создания документа в текстовом редакторе пользователь вводит символы с клавиатуры
Редактирование документа производится путём копирования, перемещения или удаления выделенных символов или фрагментов текста. Чтобы заменить одно многократно встречающееся слово на другое: [Правка – Заменить]
Вставка объектов в документ Механизм встраивания и внедрения объектов (OLE – Object Linking Embedding) позволяет копировать и вставлять объекты из одного приложения в другое [Вставка – Объект]
Проверка орфографии и синтаксиса Для проверки орфографии и синтаксиса используются специальные программные модули, которые включаются в состав текстовых процессоров и редакционноиздательских систем. Наиболее часто встречающиеся опечатки исправляет функция Автозамена
Форматы текстовых файлов Формат файла определяет способ хранения текста в файле Для преобразования текстового файла из одного формата в другой используют программы - конверторы Форматы текстовых файлов Универсальные (могут быть прочитаны большинством редакторов) Оригинальные (используются отдельными текстовыми редакторами)
Наиболее распространенные форматы текстовых файлов Только текст (Text Only) (TXT) Текст в формате RTF (Rich Text Format) Документ Word (DOC) Works 4. 0 для Windows (WPS) HTML-документ (HTM, HTML)
Сохранение и открытие документа в определенном формате Ввести команду [Файл – Сохранить как] Присвоить документу имя Выбрать в перечне требуемый формат
Выбор параметров страницы Ø Существуют две возможные ориентации страницы: книжная и альбомная Ø На странице можно устанавливать требуемые размеры полей, использовать колонтитулы [Файл – Параметры страницы] Ø Страницы документа требуется нумеровать [Вставка - Номера страниц]
Форматирование абзацев В компьютерных документах абзац – любой текст, заканчивающийся управляющим символом (маркером) конца абзаца. Ввод конца абзаца обеспечивается нажатием {Enter}.
Выравнивание абзацев Выравнивание отражает расположение текста относительно границ полей страницы. Чаще всего используют четыре способа выравнивания абзацев: По левому краю – левый край ровный, а правый рваный. По центру – оба края имеют неровные очертания, однако каждая строка абзаца симметрична относительно середины. По правому краю – правый край ровный, а левый рваный. По ширине – оба края ровные, то есть располагаются точно по границам страницы. В этом случае последняя строка абзаца ведет себя как при левостороннем выравнивании.
Отступы и интервалы Чаще всего абзац начинается отступом первой строки. Весь абзац целиком может иметь отступы слева и справа, которые отмеряются от границ полей страницы. Для выравнивания абзаца ввести команду [Формат – Абзац]
Списки применяются для размещения в документе различных перечней. Существуют списки различных типов: Нумерованные списки, когда элементы списка сопровождаются арабскими или римскими числами и буквами; Маркированные списки, когда элементы списка отмечаются с помощью специальных символов-маркеров. Возможно создание и вложенных списков, причем вкладываемый список может по своему типу отличаться от основного. Ввести команду [Формат-Список] и на диалоговой панели Списки на вкладке Многоуровневый выбрать требуемый тип многоуровневого списка.
Таблицы Таблица – объект, состоящий из строк и столбцов, на пересечении которых образуются ячейки. С помощью таблиц можно форматировать документы. При размещении в таблице чисел можно производить над ними вычисления. Преобразовать имеющийся текст в таблицу можно с помощью команды [Таблица - Преобразовать в таблицу] Вставить документ в таблицу: [Таблица – Вставить в таблицу] Автоматически отформатировать внешний вид таблицы: [Таблица – Автоформат] Форматирование таблицы вручную: [Формат – Границы и заливка] Задать точную ширину столбца: [Таблица – Высота и ширина ячейки]
Форматирование символов Символы являются теми основными объектами, из которых состоит документ. Символы – это буквы, цифры, пробелы, знаки пунктуации, специальные символы. Символы можно форматировать. Основные свойства символов: шрифт, размер, начертание и цвет.
Гипертекст позволяет структурировать документ путем выделения в нем слов-ссылок (гиперссылок). Гиперссылка состоит из двух частей: указателя ссылки и адресной части ссылки. Указатель ссылки – объект, который визуально выделяется в документе. Адресная часть гиперссылки представляет собой название закладки в документе, на который указывает ссылка. Для создания гиперссылки: ввести команду [Вставка-Гиперссылка].
Компьютерные словари и системы машинного перевода текстов Компьютерные словари могут содержать переводы сотен тысяч слов и словосочетаний, а также предоставляют пользователю дополнительные возможности: § словари могут являться многоязычными § словари могут кроме основного словаря общеупотребительных слов содержать десятки специализированных словарей по областям знаний § словари обеспечивают быстрый поиск словарных статей § словари могут являться мультимедийными. Среди российских словарей следует выделить словарь Lingvo, который содержит более 1, 2 миллиона слов и словосочетаний, систему электронных словарей «Контекст» и словарь «Мультилекс» .
Системы машинного перевода осуществляют перевод текстов, основываясь на формальном «знании» языка и использовании словарей. Лучшими среди российских систем машинного перевода считаются PROMT и «Сократ» .
Системы оптического распознавания документов Системы оптического распознавания символов (Fine. Reader, Cunei. Form) Системы оптического распознавания форм Системы распознавания рукописного текста (продукты фирмы Apple)
Слово -> строка -\n>\nабзац -> страница -\n>фрагмент..jpg","smallImageUrl":"http:\/\/pedsovet.su\/\/_load-files\/load\/16\/33\/8\/f\/2-page-10_300.jpg"},{"number":11,"text":"Символ\n- минимальная единица текстовой информации.\nКаждый символ имеет свой код.\nСоответствие между кодами и символами\nустанавливается специальными кодировочными\nтаблицами, причем в разных кодировочных\nтаблицах одному и тому же коду ставятся в\nсоответствие разные символы..jpg","smallImageUrl":"http:\/\/pedsovet.su\/\/_load-files\/load\/16\/33\/8\/f\/2-page-11_300.jpg"},{"number":12,"text":"Слово\n- произвольная последовательность\nсимволов (букв, цифр и др.),\nограниченная с двух сторон служебными\nсимволами (пробел, запятая, скобки и\nдр..jpg","smallImageUrl":"http:\/\/pedsovet.su\/\/_load-files\/load\/16\/33\/8\/f\/2-page-12_300.jpg"},{"number":13,"text":"Строка\n-\nпроизвольная\nпоследовательность\nсимволов между левой и правой границами\nдокумента..jpg","smallImageUrl":"http:\/\/pedsovet.su\/\/_load-files\/load\/16\/33\/8\/f\/2-page-13_300.jpg"},{"number":14,"text":"Абзац\n- произвольная последовательность\nсимволов, завершающаяся специальным\nсимволом конца абзаца.\nДопускаются пустые абзацы..jpg","smallImageUrl":"http:\/\/pedsovet.su\/\/_load-files\/load\/16\/33\/8\/f\/2-page-14_300.jpg"},{"number":15,"text":"Фрагмент\n- это некоторое количество рядом стоящих\nсимволов, которые можно рассматривать как\nединое целое.\nФрагментом может быть отдельное слово,\nстрока, абзац, страница и даже весь\nвводимый текст..jpg","smallImageUrl":"http:\/\/pedsovet.su\/\/_load-files\/load\/16\/33\/8\/f\/2-page-15_300.jpg"},{"number":16,"text":"Этапы создания документа на\nкомпьютере:\n1. \n\nСоздание документа\n\n2. Задание параметров страницы\n3.\n\nЗадание режима отображения\nдокумента\n\n4. Набор текста\n5. Редактирование документа\n6. Форматирование документа\n7..jpg","smallImageUrl":"http:\/\/pedsovet.su\/\/_load-files\/load\/16\/33\/8\/f\/2-page-16_300.jpg"},{"number":17,"text":"Подготовка документа\nПодготовка документа на\nкомпьютере состоит из таких\nэтапов, как:\n- набор\n- редактирование\n- форматирование..jpg","smallImageUrl":"http:\/\/pedsovet.su\/\/_load-files\/load\/16\/33\/8\/f\/2-page-17_300.jpg"},{"number":18,"text":"Редактирование\nРедактирование - процесс,\nкоторый позволяет добавлять,\nудалять, перемещать и\nизменять фрагменты документа..jpg","smallImageUrl":"http:\/\/pedsovet.su\/\/_load-files\/load\/16\/33\/8\/f\/2-page-18_300.jpg"},{"number":19,"text":"Форматирование\nФорматирование - это любые\nоперации по приданию документу\nтакого вида, который он будет\nиметь на бумаге.\nФорматирование - это изменение\nвнешнего вида документа без\nизменения его содержания..jpg","smallImageUrl":"http:\/\/pedsovet.su\/\/_load-files\/load\/16\/33\/8\/f\/2-page-19_300.jpg"},{"number":20,"text":"Форматирование\nA)\n\nФорматирование страницы.\n\nМожно сделать с помощью команды [Файл -\nпараметры страницы...]. Форматирование\nстраницы производится по следующим\nпараметрам:\n формат (размер) бумаги. По умолчанию -\nобычно А4;\n ориентация: книжная (вертикальная) и\nальбомная (горизонтальная);\n поля - расстояние от края страницы до\nграницы текстовой области..jpg","smallImageUrl":"http:\/\/pedsovet.su\/\/_load-files\/load\/16\/33\/8\/f\/2-page-20_300..jpg","smallImageUrl":"http:\/\/pedsovet.su\/\/_load-files\/load\/16\/33\/8\/f\/2-page-21_300..jpg","smallImageUrl":"http:\/\/pedsovet.su\/\/_load-files\/load\/16\/33\/8\/f\/2-page-22_300..jpg","smallImageUrl":"http:\/\/pedsovet.su\/\/_load-files\/load\/16\/33\/8\/f\/2-page-23_300.jpg"},{"number":24,"text":"Форматирование\nБ) Форматирование абзаца.\nС помощью команды [Формат - Абзац...] задаются основные\nпараметры абзаца:\n отступ слева и справа- задается относительно полей страницы. А\n красная строка - можно задать отступ, выступ или нулевую;\n выравнивание на странице (задается в пределах отступа)- по\nлевому краю, по центру, по правому краю и по ширине страницы;\n интервал перед и после - задается расстояние до предыдущего и\nпоследующего абзацев;\n междустрочный интервал - задает расстояние между строками\nвнутри абзаца..jpg","smallImageUrl":"http:\/\/pedsovet.su\/\/_load-files\/load\/16\/33\/8\/f\/2-page-24_300..jpg","smallImageUrl":"http:\/\/pedsovet.su\/\/_load-files\/load\/16\/33\/8\/f\/2-page-25_300..jpg","smallImageUrl":"http:\/\/pedsovet.su\/\/_load-files\/load\/16\/33\/8\/f\/2-page-26_300..jpg","smallImageUrl":"http:\/\/pedsovet.su\/\/_load-files\/load\/16\/33\/8\/f\/2-page-27_300..jpg","smallImageUrl":"http:\/\/pedsovet.su\/\/_load-files\/load\/16\/33\/8\/f\/2-page-28_300..jpg","smallImageUrl":"http:\/\/pedsovet.su\/\/_load-files\/load\/16\/33\/8\/f\/2-page-29_300..jpg","smallImageUrl":"http:\/\/pedsovet.su\/\/_load-files\/load\/16\/33\/8\/f\/2-page-30_300..jpg","smallImageUrl":"http:\/\/pedsovet.su\/\/_load-files\/load\/16\/33\/8\/f\/2-page-31_300.jpg"},{"number":32,"text":"Форматирование\nB) Форматирование символов.\nКоманда [Формат- Шрифт...], позволяет\nотформатировать шрифт по таким параметрам:\n гарнитура, или собственно тип шрифта;\nСтиль изображения букв называется гарнитурой.\n \n\nразмер. Размер шрифта измеряется в пунктах. Это\nисторически сложившаяся в издательском деле\nединица измерения, 1 пт = 0,376мм;\n\n начертание - может быть полужирным, курсивным,\nкурсивным полужирным или нормальным..jpg","smallImageUrl":"http:\/\/pedsovet.su\/\/_load-files\/load\/16\/33\/8\/f\/2-page-32_300..jpg","smallImageUrl":"http:\/\/pedsovet.su\/\/_load-files\/load\/16\/33\/8\/f\/2-page-33_300..jpg","smallImageUrl":"http:\/\/pedsovet.su\/\/_load-files\/load\/16\/33\/8\/f\/2-page-34_300..jpg","smallImageUrl":"http:\/\/pedsovet.su\/\/_load-files\/load\/16\/33\/8\/f\/2-page-35_300.jpg"},{"number":36,"text":"Тип шрифта\n\nСтиль изображения букв называется гарнитурой..jpg","smallImageUrl":"http:\/\/pedsovet.su\/\/_load-files\/load\/16\/33\/8\/f\/2-page-36_300..jpg","smallImageUrl":"http:\/\/pedsovet.su\/\/_load-files\/load\/16\/33\/8\/f\/2-page-37_300..jpg","smallImageUrl":"http:\/\/pedsovet.su\/\/_load-files\/load\/16\/33\/8\/f\/2-page-38_300.jpg"},{"number":39,"text":"Размер шрифта (кегль)\nФормат – шрифт ….\n\nЕдиница измерения, 1 пт = 1\/72 дюйма = 0,376мм..jpg","smallImageUrl":"http:\/\/pedsovet.su\/\/_load-files\/load\/16\/33\/8\/f\/2-page-39_300..jpg","smallImageUrl":"http:\/\/pedsovet.su\/\/_load-files\/load\/16\/33\/8\/f\/2-page-40_300.jpg"},{"number":41,"text":"Начертание\nФормат – шрифт …..jpg","smallImageUrl":"http:\/\/pedsovet.su\/\/_load-files\/load\/16\/33\/8\/f\/2-page-41_300.jpg"},{"number":42,"text":"Начертание\n\nНормальный шрифт ничем не\nвыделяется.\nПолужирный шрифт темнее, он\nхорошо заметен.\nКурсивный шрифт имеет наклон..jpg","smallImageUrl":"http:\/\/pedsovet.su\/\/_load-files\/load\/16\/33\/8\/f\/2-page-42_300.jpg"},{"number":43,"text":"Другие параметры форматирования\nКроме этих основных\nможно задать еще ряд\nдополнительных\nпараметров или\nэффектов: цвет, верхний\nили нижний индекс,\nподчеркивание и пр..jpg","smallImageUrl":"http:\/\/pedsovet.su\/\/_load-files\/load\/16\/33\/8\/f\/2-page-43_300.jpg"},{"number":44,"text":"Сохранение документа\nКоманда Файл – Сохранить как…..jpg","smallImageUrl":"http:\/\/pedsovet.su\/\/_load-files\/load\/16\/33\/8\/f\/2-page-44_300.jpg"},{"number":45,"text":"Сохранение документа\nСпособ записи текста в память компьютера называется\nформатом файла.\nНаиболее распространены следующие форматы текстовых\nфайлов:\n ТХТ - сохраняет текст без форматирования, в текст\nвставляются только управляющие символы конца абзаца;\n RTF - универсальный формат, сохраняющий всё\nформатирование; преобразует управляющие коды в\nтекстовые команды, которые могут быть прочитаны и\nинтерпретированы многими приложениями; по сравнению с\nдругими\nформатами\nимеет\nдостаточно\nбольшой\nинформационный объем;\n DOC - оригинальный формат документов MS Word;\n HTML\n-\nформат,\nиспользуемый\nдля\nхранения\nWeb-страниц; содержит коды разметки языка гипертекста..jpg","smallImageUrl":"http:\/\/pedsovet.su\/\/_load-files\/load\/16\/33\/8\/f\/2-page-45_300.jpg"},{"number":46,"text":"Печать документа\nДля вывода документа на бумагу к компьютеру\nподключается\nпечатающее\nустройство\n-\nпринтер.\nСуществуют различные типы принтеров.\nМатричный принтер печатает с помощью металлических\nиголок, которые прижимают к бумаге красящую ленту.\nСтруйный принтер наносит буквы на бумагу, распыляя над\nней капли жидких чернил. С его помощью создаются не\nтолько черно-белые, но и цветные изображения.\nВ лазерном принтере для печати символов используется\nлазерный луч. Это позволяет получать типографское\nкачество печати..jpg","smallImageUrl":"http:\/\/pedsovet.su\/\/_load-files\/load\/16\/33\/8\/f\/2-page-46_300..jpg","smallImageUrl":"http:\/\/pedsovet.su\/\/_load-files\/load\/16\/33\/8\/f\/2-page-47_300.jpg"},{"number":48,"text":"Домашнее задание\n§ 9.1, 9..jpg","smallImageUrl":"http:\/\/pedsovet.su\/\/_load-files\/load\/16\/33\/8\/f\/2-page-48_300.jpg"}]">
Поиск (в широком смысле) 1) действия субъекта, направленные на получение нового или утерянного (забытого): новой информации, данных, сведений, знаний открытие закономерностей действия по раскрытию (осознанию) скрытых содержаний, недостающих для целостного состояния (действие по восстановлению целостности) 2) один из способов обучения, обеспечивающих возможность получения знаний через самостоятельные мыслительные действия для решения возникающих задач 3
Понятия поиска (2) Поиск данных раздел информатики, изучающий алгоритмы для поиска и обработки информации как в структурированных (базы данных) так и неструктурированных (текстовый документ) данных Информационный поиск (англ. Information retrieval) процесс поиска неструктурированной документальной информации, удовлетворяющей информационные потребности, и наука об этом поиске Поиск информации процесс выявления в массиве информации записей, удовлетворяющих заранее определенному условию поиска или запросу Термин был впервые введён Кельвином Муром в
Поиск как наука Алгоритмы и структуры данных Машинное обучение (Machine Learning) НИУ ВШЭ Факультет бизнес - информатики Базовая кафедра Яндекс. Курсы магистратуры: Web- графы и поиск Алгоритмы и структуры данных для поиска Анализ символьных последовательностей Многомерный статистический анализ 5
Виды поиска полнотекстовый - поиск по всему содержимому документа по метаданным - поиск по атрибутам документа (название, дата создания, размер, автор и т. д.) поиск изображений – распознавание объектов, лиц Существует путаница, связанная с понятиями поиска данных, поиска документов, информационного поиска и текстового поиска. 8
Оценки эффективности. Выпадение (fall-out) Выпадение характеризует вероятность нахождения нерелевантного ресурса и определяется, как отношение числа найденных нерелевантных документов к общему числу нерелевантных документов в базе 14 где D nrel это множество нерелевантных документов в базе, а множество документов, найденных системой
Стратегии поиска. Классификация. Индексы Классификатор (индекс) систематизированный перечень наименованных объектов, каждому из которых в соответствие дан уникальный код (индекс) Методы: Иерархический Фасетный Кодирование - присвоение кода классификационной группировке или объекту классификации. Методы: Порядковый Серийно - порядковый Последовательный Параллельный 16
Пример: индекс в БД объект базы данных, создаваемый с целью повышения производительности поиска данных Индекс формируется из значений одного или нескольких столбцов таблицы и указателей на соответствующие строки таблицы и, таким образом, позволяет искать строки, удовлетворяющие критерию поиска Ускорение работы с использованием индексов достигается за счёт того, что индекс имеет структуру, оптимизированную под поиск например, сбалансированного дерева, В - дерева и т. д. 17
Стратегии поиска. Деревья Двоичное дерево древовидная структура данных, в которой каждый узел имеет не более двух потомков (детей) Двоичное дерево поиска это двоичное дерево, для которого выполняются следующие дополнительные условия (свойства дерева поиска): Оба поддерева левое и правое, являются двоичными деревьями поиска У всех узлов левого поддерева произвольного узла X значения ключей данных меньше, нежели значение ключа данных самого узла X В то время, как у всех узлов правого поддерева того же узла X значения ключей данных не меньше, нежели значение ключа данных узла X 18
Двоичное дерево поиска (2) Двоичное дерево состоит из узлов записей вида (data, left, right), где data некоторые данные, привязанные к узлу, left и right ссылки на узлы, являющиеся детьми данного узла - левый и правый сыновья соответственно Данные (data) обладают ключом (key), на котором определена операция сравнения " меньше ". В конкретных реализациях это может быть пара (key, value) - (ключ и значение), или ссылка на такую пару, или простое определение операции сравнения на необходимой структуре данных или ссылке на неё 19
Двоичное дерево поиска (3) Поиск элемента (FIND) Дано: дерево Т и ключ K Задача: проверить, есть ли узел с ключом K в дереве Т, и если да, то вернуть ссылку на этот узел Алгоритм: Если дерево пусто, сообщить, что узел не найден, и остановиться Иначе сравнить K со значением ключа корневого узла X Если K=X, выдать ссылку на этот узел и остановиться Если K>X, рекурсивно искать ключ K в правом поддереве Т Если K
X, рекурсивно искать ключ K в правом поддереве Т Если K">
Стратегии поиска. Хэширование преобразование по детерминированному алгоритму входного массива данных произвольной длины в выходную битовую строку фиксированной длины Такие преобразования также называются хеш - функциями или функциями свёртки, а их результаты называют хешем, хеш - кодом или сводкой сообщения Если у двух строк хеш - коды разные, строки гарантированно различаются, если одинаковые строки, вероятно, совпадают Предложил сотрудник IBM Хансу Петер Лун в январе 1953 года 21
Хэширование (2) Существует множество алгоритмов хеширования с различными свойствами (разрядность, вычислительная сложность, криптостойкость и т. п.) Простейшие примеры хеш - функций: контрольная сумма или CRC Хорошая хеш - функция должна удовлетворять двум свойствам: 1. Быстро вычисляться 2. Минимизировать количество коллизий Коллизией хеш - функции H называется два различных входных блока данных x и y таких, что H(x) = H(y) 22
Хэширование. Виды (3) Хеш - функции основанные на делении H (k) = k mod m Мультипликативная схема хеширования Хеширование строк переменной длины (Хеширование Пирсона) Универсальное хеширование - используется не одна конкретная хеш - функция, а происходит выбор из заданного семейства по случайному алгоритму 23
Хэширование. Хэш - таблицы (3) Хеш - таблицей называется структура данных, позволяющая хранить пары вида (ключ, хеш - код) и поддерживающая операции поиска, вставки и удаления элемента Бытовым аналогом хеширования в данном случае может служить помещение слов в словаре по алфавиту. Первая буква слова является его хеш - кодом, и при поиске мы просматриваем не весь словарь, а только нужную букву 24
Информационный поиск (Information retrieval) Документ - некий объект, содержащий информацию в зафиксированном виде (тексты на естественном или формализованном языке, изображения, звуковая информация и т. д.) Запрос - формализованный способ выражения информационных потребностей пользователя системы (языки поисковых запросов, синтаксис которых варьируется) Релевантность - функция соответствия документа запросу, субъективна 25
Векторная модель Реализована в 1968 Джерардом Солтоном (Gerard Salton) в поисковой системе SMART Снова коллекция документов, каждый из которых теперь является мультимножеством слов Матрица M, где M ij = TF ij · IDF i, где: Частота терма TF ij относительная доля слова i в тексте j Обратная встречаемость в документах IDF i величина, обратная количеству документов, содержащих слово i Физический смысл M ij степень соответствия слова i тексту j Запрос: t 3 AND t 5 (разрешаем только AND) 28
Вероятностная модель Робертсон (Robertson) и Спарк - Джоунз (Sparck-Jones) в 1977 г. Релевантность – здесь вероятность того, что данный документ может оказаться интересным пользователю Документ: множество слов D = {d 1,..., d n } Запрос: Q k тоже, но храним как множество Соответствие: Зафиксируем запрос Q k Пусть есть распределение вероятностей на всех текстах быть релевантным запросу Q k: обозначаем P(R|Q k,D) Пусть есть распределение вероятностей на всех текстах быть НЕрелевантным запросу Q k: обозначаем P(|Q k,D) Функцией соответствия будет их отношение (или логарифм этой дроби) 29
Поиск в Вебе Нужно анализировать не только текст документа, но и off-page факторы: положение на сайте посещаемость авторитетность источника частота обновления цитируемость страницы и ее авторов Искусственное накручивание рейтинга страниц (SEO) Поиск в полуструктурированных данных 30
Полуструктурированные данные 1) такой способ хранения данных, при котором у каждой единицы информации может быть произвольный набор полей 2) данные без постоянной чётко определённой структуры, либо данные со структурой, неизвестной пользователю. Их удобно представлять в виде графа 31
XML XML (eXtensible Markup Language) – язык текстовой разметки, стандартизованный W3C, удобный для представления полуструктурированных данных 32 XML and IR: A SIGIR 2000 Workshop David Carmel, Yoelle Maarek, Aya Soffer XQL and Proximal Nodes Ricardo Baeza-Yates Gonzalo Navarro bla... bla... bla... Querying XML in Xyleme bla...
Качество ранжирования веб - страниц PageRank это алгоритм, позволяющий оценить, насколько данная интернет - страница популярна предложен Брином и Пейджем в 1998 г. идея: определять рейтинг страницы через количество ведущих на нее ссылок и рейтинг ссылающихся страниц 35
Семантический поиск Семантический Веб новая концепция развития Веба и сети Интернет, принятая и продвигаемая W3C Проблема: большинство данных в Вебе хранится в форме, рассчитанной на восприятие человеком, их структура не очевидна роботу Семантический Веб это не отдельная сеть, а расширение уже существующей 37
Принципы работы Агент программа, работающая без непосредственного управления со стороны человека или другого постоянного контроля, созданная для достижения целей, поставленных перед ней пользователем Закажи для меня эту книгу в ближайшей библиотеке. Посмотри на расписание электричек и мое расписание и выбери билеты в театр, чтобы я мог успеть после работы. Скажи мне, какое вино нужно купить к каждому из блюд в этом меню. И кстати, я не люблю Сотерн. Микроволновка, сходи на сайт производителя и загрузи оптимальные параметры подогрева. 38
Сценарии использования Семантический поиск. Поисковая система сможет выдавать только те сайты, где упоминается в точности искомое понятие, а не произвольные страницы, в тексте которых встретилось данное многозначное ключевое слово. Объединение знаний (интеграция баз данных) Всепроникающие вычисления (ubiquitous computing). Расширение сферы влияния на физический мир 39
Основная цель Семантического Веба создание языка, на котором можно будет описать как данные, так и правила рассуждений об этих данных, так что правила вывода, существующие в какой - либо системе представления знаний, можно будет экспортировать в Веб синтаксис семантика XML – есть синтаксис, но не определена семантика! Тим Бернерс - Ли 40
Структура языка RDF (Resource Description Framework) язык, отвечающий за синтаксис документов Семантического Веба. В нем широко используются ссылки на онтологии для определения смысла слов OWL (Ontology Web Language) язык описания онтологий. Онтология описание классов объектов, их свойств и взаимоотношений для какой - то предметной области (домена) 41
План реализации 1. Синтаксис для представления знаний, использующий ссылки на онтологии (сделано: RDF) 2. Язык описания онтологий (сделано: OWL) 3. Язык описания веб - сервисов (начато: WSDL, OWL-S) 4. Инструменты чтения и разработки документов Семантического Веба (начато: Jena, Haystack, Protege) 5. Язык запросов к знаниям, записанным в RDF (начато: SPARQL) 6. Логический вывод знаний (не сделано). 7. Семантическая поисковая система (начато: SHOE). 8. Агенты Семантического Веба (не сделано). 42
RDF: синтаксис Семантического Веба XML дает возможность создавать документы произвольной структуры, однако данный язык ничего не говорит о том, что означает эта структура RDF кодирует смысл при помощи деревьев глубины три (Notation3), где каждое дерево состоит из: субъекта (подлежащее) свойства (сказуемое) объекта (дополнение) « Небо голубого цвета » = субъект « небо », свойство « иметь цвет », объект « голубой » 44
Пример: RSS RSS семейство XML- форматов, предназначенных для описания лент новостей, анонсов статей, изменений в блогах и т. п. Информация из различных источников, представленная в формате RSS, может быть собрана, обработана и представлена пользователю в удобном для него виде специальными программами - агрегаторами. Под RSS может пониматься: Rich Site Summary богатая сводка сайта RDF Site Summary сводка сайта с применением инфраструктуры описания ресурсов Really Simple Syndication очень простая синдикация 45
Обработка естественного языка Natural Language Processing, NLP - технологии обработки естественных языков Question-Answering Systems, QAS - вопросно - ответные системы На вход такой системе подаётся запрос, сформулированный на естественном языке, после чего он обрабатывается с использованием методов NLP, и генерируется естественно - языковой ответ 46
Проблемы создания QAS Типы вопросов Обработка вопросов Контекстные вопросы Источники знаний для QA- системы Выделение ответов Формулировка ответа (слияние ответов из разных документов) Ответы на вопросы в реальном времени Многоязыковые запросы Интерактивность Механизм рассуждений (вывода) Профили пользователей QA- систем 48
Поиск изображений по содержанию англ. Content-based image retrieval (CBIR) раздел компьютерного зрения, решающий задачу поиска изображений, которые имеют требуемое содержание, в большом наборе цифровых изображений Алгоритм поиска должен анализировать содержание изображения, например, цвет представленных на нём объектов, их форму, текстуру, композицию сцены Термин «Content-based image retrieval» впервые был введен в употребление в 1992 г. Т. Като Альтернатива: методы, основанные исключительно на категоризации метаданных (не подходит к автомтически созданным изображениям, камеры наблюдений) 49
Области применения Поиск изображений в сети интернет Каталогизация изображений произведений искусства Организация работы с архивами фотографических снимков Организация каталогов розничной продажи товаров Медицинская диагностика заболеваний Предотвращение преступлений и беспорядков Военно - оружейное применение Вопросы контроля за распространением интеллектуальной собственности Получение информации о местоположении удаленных зондов и географическое позиционирование Контроль за содержимым массивов изображений 50
Общая схема система производит поиск на основе входного изображения, указываемого пользователем все результирующие экземпляры изображений должны иметь общие элементы с входом, указанным пользователем пользователь может подать на вход как существующее изображение, так и грубый набросок требуемого результата 51
Описание содержания. Цвет Поиск изображений с помощью сравнения цветовых составляющих производится с помощью построения гистограммы их распределения изображение делится на регионы по сходным цветовым характеристикам, и далее учитывается их взаимное расположение 52
Источники Дональд Кнут. Искусство программирования, том 3. Сортировка и поиск /The Art of Computer Programming, vol.3. Sorting and Searching./ 2- е изд. М.: « Вильямс », С MIT OpenCourseWare Школа анализа данных Яндекс Юрий Лифшиц - курс " Алгоритмы для Интернета " Илья Сегалович « Как работают поисковые системы »
Спасибо за внимание! 57
