Чтобы пользоваться предварительным просмотром презентаций создайте себе аккаунт (учетную запись) Google и войдите в него: https://accounts.google.com
Подписи к слайдам:
Технология обработки текстовой информации Лекция 8
ЧТО ТАКОЕ ТЕКСТОВЫЙ РЕДАКТОР И ТЕКСТОВЫЙ ПРОЦЕССОР? Текстовые редакторы и текстовые процессоры предназначены для создания, редактирования, форматирования, сохранения во внешней памяти и печати текстовых документов. Обычно текстовыми редакторами принято называть программы, выполняющие простейшие операции по редактированию текста, а текстовыми процессорами - программы, обладающие расширенными по сравнению с редакторами возможностями для компьютерной обработки текста.
НАЗНАЧЕНИЕ ТЕКСТОВОГО ПРОЦЕССОРА создание документов редактирование документов сохранение документов форматирование документов печать документов автоматическое составление оглавлений и указателей создание и форматирование таблиц внедрение в документ рисунков, формул и др. проверка пунктуации и орфографии
ВОЗМОЖНОСТИ ТЕКСТОВОГО ПРОЦЕССОРА Поддержка двух и более языков с возможностью редактировать синтаксически и стилистически; Использование разнообразных шрифтов и изменение их размера, цвета, начертания; Использование в одном документе символов разных языков; Работа с несколькими документами и несколькими средами (графический, текстовый редакторы, электронные таблицы, базы данных, презентации и т.д.); Большой выбор объектов, которые можно вставить в документ; Автоматическое разбиение документа на страницы; Добавление списков, гиперссылок, сносок, колонтитулов; Расширенные возможности работы с таблицей и т.д.
ОСНОВНЫЕ ЭЛЕМЕНТЫ ТЕКСТОВОГО ДОКУМЕНТА символ - минимальная единица текстовой информации; слово - произвольная последовательность букв и цифр, ограниченная с двух сторон служебными символами; строка - произвольная последовательность символов между левой и правой границами абзаца; предложение - произвольная последовательность слов, завершающаяся точкой; абзац - часть текста, которая завершается специальным символом конца абзаца, при этом допускаются пустые абзацы; страницу составляют строки и абзацы, таблицы и внедренные в документ объекты; наиболее крупной единицей является собственно документ, где все составляющие его абзацы определенным образом структурированы, снабжены при необходимости заголовками, выстроена иерархия структурных разделов.
Текстовый процессор OpenOffice.org Writer
Текстовый процессор MS Word
ЗАПУСК ПРОГРАММЫ OOO WRITER Способ 1 . Пуск → Все программы → OpenOffice.org → OpenOffice.org Writer Способ 2 . Пуск → Все программы → OpenOffice.org → в диалоговом окне выбрать пункт Текстовый документ Способ 3 . Нажать на значок OpenOffice.org на Панели задач Способ 4 . ПКМ на свободном месте → Создать→ Текстовый документ OpenDocument
ЗАПУСК ПРОГРАММЫ MS WORD Способ 1 . Пуск → Все программы → Microsoft Office → Microsoft Office Word 2007 Способ 2 . Нажать на значок MS Word на Панели задач Способ 3 . ПКМ на свободном месте → Создать→ Документ Microsoft Office Word
ОКНО OOO WRITER
ОКНО MS WORD
СОЗДАНИЕ ДОКУМЕНТА В OOO WRITER Способ 1. При запуске программы создается новый документ, который по умолчанию называется «Без имени 1 . odt » Способ 2. На Стандартной панели инструментов кнопка Создать Способ 3. Если OOO Writer уже запущен: Файл → Создать → Текстовый документ
СОЗДАНИЕ ДОКУМЕНТА В MS WORD Способ 1. При запуске программы создается новый документ, который по умолчанию называется «Документ. docx » Способ 2. На Стандартной панели инструментов кнопка Создать Способ 3. Если MS Word уже запущен: Меню → Создать → Новый документ → Создать
СОЗДАНИЕ ДОКУМЕНТА ИЗ ШАБЛОНА В OOO WRITER Для создания нового документа в OOO Writer можно использовать шаблоны. Шаблоны служат основой для ряда документов, обеспечивая их одинаковую разметку. Поэтому все они выглядят одинаково; они имеют те же самые верхние и нижние колонтитулы, используют одинаковые шрифты и пр. К существующим шаблонам можно добавлять новые и использовать их для создания новых документов. Кроме того, большое количество шаблонов можно загрузить из Интернета. После создания нового шаблона можно создавать новые документы, используя его с помощью меню Файл → Создать → Шаблоны и документы. Откроется окно, в котором можно выбрать шаблон, необходимый для создания документа. Выделите шаблон, затем щелкните по кнопке Открыть. Будет создан новый документ, использующий форматы, определенные в этом шаблоне.
СОЗДАНИЕ ДОКУМЕНТА ИЗ ШАБЛОНА В MS WORD Для создания нового документа в MS Word можно использовать шаблоны. Шаблоны служат основой для ряда документов, обеспечивая их одинаковую разметку. После создания нового шаблона можно создавать новые документы, используя его с помощью меню Создать → Шаблоны → Выбрать группу шаблонов → Выбрать шаблон → Создать. Будет создан новый документ, использующий форматы, определенные в этом шаблоне.
СОХРАНЕНИЕ ДОКУМЕНТА В OOO WRITER Файл → Сохранить как… в появившемся окне в поле «Имя файла» необходимо ввести название файла, затем нажать на кнопку «Сохранить». Применяется при первичном сохранении документа. Файл → Сохранить. Данную команду используют при сохранений изменений в уже существующем документе. Кнопка Сохранить на Стандартной панели инструментов Сохранение документа в другом формате: Файл Сохранить как… → в поле Тип файла из раскрывающегося списка выбрать формат.
СОХРАНЕНИЕ ДОКУМЕНТА В MS WORD Меню Office → Сохранить как… в появившемся окне в поле «Имя файла» необходимо ввести название файла, затем нажать на кнопку «Сохранить». Применяется при первичном сохранении документа. Меню Office → Сохранить. Данную команду используют при сохранений изменений в уже существующем документе. Кнопка Сохранить на Стандартной панели инструментов Сохранение документа в другом формате: Меню Office Сохранить как… → в поле Тип файла из раскрывающегося списка выбрать формат.
ВВОД И РЕДАКТИРОВАНИЕ ТЕКСТА OOO Writer позволяет набирать текст в двух режимах: в режиме вставки и в режиме замены. Переключаются эти режимы с помощью клавиши. Если при наборе текста сделаны ошибки, их можно устранить следующим образом: если стираемая буква (или буквы) находятся слева от курсора ввода надо воспользоваться клавишей, если справа - ; для удаления всего текста, который был только что введен, можно воспользоваться командой "Отменить" из меню правка или нажать сочетание клавиш; можно отменить одно или сразу несколько ранее выполненных действий, воспользовавшись кнопкой " Отменить " на стандартной панели инструментов.
ВЫДЕЛЕНИЕ двойное нажатие ЛКМ на слове – выделяет слово тройное нажатие ЛКМ на слове – выделяет абзац Shift + стрелки на клавиатуре – посимвольное выделение в выбранном направлении Shift + Home – выделение до начала строки Shift + End – выделение до конца строки нажать ЛКМ и, удерживая, вести мышку для выделения всего Правка → Выделить всё
ФОРМАТИРОВАНИЕ В OOO WRITER Способ 1. Выделить необходимый фрагмент и воспользоваться панелью Форматирования, или контекстным меню, или пунктом Главного меню Формат. Способ 2. Выставить необходимые параметры форматирования с помощью панели Форматирования, или контекстного меню, или пункта Главного меню Формат. Способ 3. Использование стилей форматирования
ФОРМАТИРОВАНИЕ В MS WORD Способ 1. Выделить необходимый фрагмент и воспользоваться панелью Форматирования, или контекстным меню. Способ 2. Выставить необходимые параметры форматирования с помощью панели Форматирования, или контекстного меню. Способ 3. Использование стилей форматирования.
СПИСКИ В OOO WRITER Процессор позволяет создавать в документе два вида списков – нумерованные и маркированные. Для этого надо воспользоваться кнопками панели Форматирования – Нумерованный список или Маркированный список или воспользоваться меню Формат.
СПИСКИ В MS WORD Процессор позволяет создавать в документе два вида списков – нумерованные и маркированные. Для этого надо воспользоваться кнопками на вкладке Главная – Нумерованный список или Маркированный список.
ВСТАВКА В OOO WRITER ГРАФИЧЕСКОГО ОБЪЕКТА В OOO Writer существует специальная панель инструментов Рисование для облегчения работы с графическими объектами. Для того, чтобы вставить рисунок из галереи OpenOffice . org Writer существуют следующие способы: Вставка → Изображение. Кнопка на Панели инструментов Рисование Для того, чтобы выполнить различные действия над фигурой ее необходимо выделить щелчком ЛКМ. Затем воспользоваться панелью настройки изображения, или контекстным меню, или меню Формат. Существуют следующие средства настройки изображения: задание формата изображения, увеличение и уменьшение контрастности, увеличение и уменьшение яркости, обрезка, поворот объекта на определенный градус, установка толщины линий, сжатие рисунка, обтекание текста, форматирование объекта и т.д.
ВСТАВКА В MS WORD ГРАФИЧЕСКОГО ОБЪЕКТА В MS Word для вставки графического объекта необходимо перейти на вкладку Вставка → Выбрать необходимое действие. Для того, чтобы вставить рисунок из галереи MS Word: Вставка → Фигуры. Для того, чтобы выполнить различные действия над фигурой ее необходимо выделить щелчком ЛКМ. Затем воспользоваться вкладкой Формат, которая автоматически появляется при выделения объекта, или вызовом контекстного меню.
ВСТАВКА ФОРМУЛЫ В OOO WRITER В OOO Writer редактор формул называется Math . Он позволяет вводить в документ и редактировать математические символы и операторы, такие как дроби, интегралы, матрицы и т.д. В редакторе формул содержится около 120 шаблонов, сгруппированных в палитры. Шаблоны можно вкладывать один в другой для построения многоступенчатых формул. Для вызова Math существует два способа: Кнопка на панели инструментов Вставка Вставка → Объект → Формула Math
ВСТАВКА ФОРМУЛЫ В MS WORD В MS Word редактор формул называется Microsoft Equation . Он позволяет вводить в документ и редактировать математические символы и операторы, такие как дроби, интегралы, матрицы и т.д. В редакторе формул содерж а тся шаблоны. Шаблоны можно вкладывать один в другой для построения многоступенчатых формул. Для вызова Microsoft Equation существует два способа: Вставка → Формула; Вставка → Объект → Microsoft Equation .
ВСТАВКА ТАБЛИЦЫ В OOO WRITER В OOO Writer существует специальная панель инструментов Таблицы для облегчения работы с таблицами. Для того, чтобы вставить таблицу существуют следующие способы: Вставка → Таблицу … Кнопка на Панели инструментов Вставка Для того, чтобы выполнить различные действия над таблицей, ее нужно выделить щелчком ЛКМ. Затем воспользоваться панелью Таблица, или контекстным меню, или меню Формат.
ВСТАВКА ТАБЛИЦЫ В MS WORD В MS Word существует специальная панель инструментов Таблицы для облегчения работы с таблицами. Для того, чтобы вставить таблицу необходимо: Вставка → Таблица Для того, чтобы выполнить различные действия над таблицей, ее нужно выделить щелчком ЛКМ. Затем воспользоваться панелью Таблица, или контекстным меню.
ПОИСК И ЗАМЕНА ТЕКСТА В OOO WRITER OOO Writer имеет подпункт меню Найти и заменить, с помощью которого можно автоматизировать процесс поиска и замены текста в документе. Чтобы отобразить диалоговое окно Найти и заменить используйте клавиши или выберите Правка → Найти и заменить.
ПОИСК И ЗАМЕНА ТЕКСТА В MS WORD MS Word имеет команда З аменить, с помощью которой можно автоматизировать процесс поиска и замены текста в документе. Чтобы отобразить диалоговое окно Найти и заменить используйте клавиши или выберите Главная → З аменить.
СОЗДАНИЕ КОЛОНТИТУЛОВ В OOO WRITER Верхний колонтитул представляет собой область, которая появляется в верхней части страницы. Нижний колонтитул появляется в нижней части страницы. В колонтитулах размещается такая информация, как номер страницы, которая появляется на каждой странице документа, имеющей этот стиль страницы. Для вставки колонтитула в пункте Главного меню Вставить выбрать нужный колонтитул Верхний колонтитул или Нижний колонтитул. Содержание колонтитул выбираются в Поля меню Вставка В верхний или нижний колонтитулы часто помещается и другая информация, такая как название документа или главы. Эти элементы лучше всего добавлять в формате полей. При этом, если что-то изменится, колонтитулы также будут автоматически изменен.
СОЗДАНИЕ КОЛОНТИТУЛОВ В MS WORD Для вставки колонтитула: Вставить выбрать нужный колонтитул Верхний колонтитул или Нижний колонтитул. Содержание колонтитул выбираются в Конструкторе.
ПАРАМЕТРЫ СТРАНИЦЫ В OOO WRITER Настройка параметров страницы осуществляется в пункте Главного меню Формат → Страница
ПАРАМЕТРЫ СТРАНИЦЫ В MS WORD Настройка параметров страницы осуществляется в пункте Разметка страницы → Параметры страницы.
ПЕЧАТЬ В OOO WRITER Для быстрой печати документа достаточно нажать кнопку Печать на Стандартной панели инструментов. Для расширенных настроек печати необходимо вызвать окно Печать: Файл → Печать…
ПЕЧАТЬ В MS WORD Для быстрой печати документа достаточно нажать кнопку Печать на Стандартной панели инструментов. Для расширенных настроек печати необходимо вызвать окно Печать: Кнопка « Office » → Печать…
САМОСТОЯТЕЛЬНАЯ РАБОТА Стили (Ривкинд И.Я., Лысенко Т.И. Информатика 10 класс, стр. 51-56) Структура документа (Ривкинд И.Я., Лысенко Т.И. Информатика 10 класс, стр. 56-60)
«Текстовый процессор» - Типы текстовых редакторов. Свободный редактор на Java. Vim. EmEditor - платный редактор для Windows-систем. TextEdit - текстовый редактор с нестандартным интерфейсом. EditPad. Свободный. HippoEdit. TextMate. Широкие возможности настройки и автоматизации. Имеет сходные возможности и удобный интерфейс.
«Обработка текстовой информации» - Строка состояния. Правила оформления объемных документов: Примеры издательских систем: Corel Ventura, Page Maker, Quarkx Press. 7. Возможности word. Форматирование - процесс придания тексту формы. Обработка текстовой информации с помощью эвм. 4. Обработка текстовой информации. 3. Оформление документов.
«Шаблоны для текста» - Сравнение языковых средств: дополнительные возможности. Альтернативы | Повторение {} Опциональное вхождение Параметры шаблона. Запись конструкций. Изучение терминологических и дискурсивных особенностей НТ прозы. NGACC [«мы»] «будем называть»tins. Дополнительные примеры. Язык lspl-шаблонов: основные возможности.
«Распознавание текста» - ABBYY FineReader. FineReader имеет массы дополнительных функций и удобный интерфес. Зачем нужны программы распознавания текста? Сканирование в сером является оптимальным режимом для системы распознавания. Оптимальное разрешение при сканировании. Какие программы распознания текста вы знаете? Программы распознавания текста.
«Текстовый документ» - Заголовки граф записывают параллельно строкам таблицы. Примеры оформления приложений. Правила оформления ссылок и сносок. Пример оформления списка литературы. Правила оформления формул и иллюстраций. 3.5 Оформление таблиц 3.5.1 Цифровой материал, как прави- ло оформляют в виде таблиц. Правила оформления текстовой части.
«Текстовая информация» - Тема: Текстовая информация. Возможности: изменение типа и размера шрифта, копирование и вставка фрагментов текста. Нельзя помиловать. Кто к нам пришел! Текстовая информация. Кто к нам пришел? Текстовый редактор «Блокнот». Задание: на листке в клетку нарисовать произвольный многоугольник. Обменяться с соседом по ряду листочками.
Всего в теме 29 презентаций
Презентация на тему "Технология обработки текстовой информации" по информатике в формате powerpoint. В данной презентации для школьников 11 класса содержится обучающий материал по работе с текстовой информацией. Автор презентации: учитель информатики, Шлямина Е.А.
Фрагменты из презентации
Создание и редактирование документов
Для обработки текстовой информации на компьютере используют приложения общего назначения – текстовые редакторы, которые позволяют создавать, редактировать, форматировать, сохранять и распечатывать текст
Создание документа
- Создание документа начинается с выбора шаблона.
- Для создания документов со сложной структурой используют Мастера
- В процессе создания документа в текстовом редакторе пользователь вводит символы с клавиатуры
Редактирование документа
- Редактирование документа производится путём копирования, перемещения или удаления выделенных символов или фрагментов текста.
- Чтобы заменить одно многократно встречающееся слово на другое: [Правка – Заменить]
Вставка объектов в документ
Механизм встраивания и внедрения объектов (OLE – Object Linking Embedding) позволяет копировать и вставлять объекты из одного приложения в другое [Вставка – Объект]
Проверка орфографии и синтаксиса
- Для проверки орфографии и синтаксиса используются специальные программные модули, которые включаются в состав текстовых процессоров и редакционно-издательских систем.
- Наиболее часто встречающиеся опечатки исправляет функция Автозамена
Форматы текстовых файлов
- Формат файла определяет способ хранения текста в файле
- Для преобразования текстового файла из одного формата в другой используют программы - конверторы
Сохранение и открытие документа в определенном формате
- Ввести команду [Файл – Сохранить как]
- Присвоить документу имя
- Выбрать в перечне требуемый формат
Выбор параметров страницы
- Существуют две возможные ориентации страницы: книжная и альбомная
- На странице можно устанавливать требуемые размеры полей, использовать колонтитулы [Файл – Параметры страницы]
- Страницы документа требуется нумеровать [Вставка - Номера страниц]
Форматирование абзацев
В компьютерных документах абзац – любой текст, заканчивающийся управляющим символом (маркером) конца абзаца. Ввод конца абзаца обеспечивается нажатием {Enter}.
Выравнивание абзацев
Выравнивание отражает расположение текста относительно границ полей страницы. Чаще всего используют четыре способа выравнивания абзацев:
- По левому краю – левый край ровный, а правый рваный.
- По центру – оба края имеют неровные очертания, однако каждая строка абзаца симметрична относительно середины.
- По правому краю – правый край ровный, а левый рваный.
- По ширине – оба края ровные, то есть располагаются точно по границам страницы. В этом случае последняя строка абзаца ведет себя как при левостороннем выравнивании.
Отступы и интервалы
- Чаще всего абзац начинается отступом первой строки. Весь абзац целиком может иметь отступы слева и справа, которые отмеряются от границ полей страницы.
- Для выравнивания абзаца ввести команду [Формат – Абзац]
Списки
Списки применяются для размещения в документе различных перечней. Существуют списки различных типов:
- Нумерованные списки, когда элементы списка сопровождаются арабскими или римскими числами и буквами;
- Маркированные списки, когда элементы списка отмечаются с помощью специальных символов-маркеров.
Возможно создание и вложенных списков, причем вкладываемый список может по своему типу отличаться от основного. Ввести команду [Формат-Список] и на диалоговой панели Списки на вкладке Многоуровневый выбрать требуемый тип многоуровневого списка.
Таблицы
- Таблица – объект, состоящий из строк и столбцов, на пересечении которых образуются ячейки. С помощью таблиц можно форматировать документы. При размещении в таблице чисел можно производить над ними вычисления.
- Преобразовать имеющийся текст в таблицу можно с помощью команды [Таблица - Преобразовать в таблицу]
- Вставить документ в таблицу: [Таблица – Вставить в таблицу]
- Автоматически отформатировать внешний вид таблицы: [Таблица – Автоформат]
- Форматирование таблицы вручную: [Формат – Границы и заливка]
- Задать точную ширину столбца: [Таблица – Высота и ширина ячейки]
Форматирование символов
- Символы являются теми основными объектами, из которых состоит документ.
- Символы – это буквы, цифры, пробелы, знаки пунктуации, специальные символы.
- Символы можно форматировать.
- Основные свойства символов: шрифт, размер, начертание и цвет.
Гипертекст
- Гипертекст позволяет структурировать документ путем выделения в нем слов-ссылок (гиперссылок).
- Гиперссылка состоит из двух частей: указателя ссылки и адресной части ссылки.
- Указатель ссылки – объект, который визуально выделяется в документе.
- Адресная часть гиперссылки представляет собой название закладки в документе, на который указывает ссылка.
- Для создания гиперссылки: ввести команду [Вставка-Гиперссылка].
Программное обеспечение. К прикладному программному обеспечению, предназначенному для работы с текстовой информацией, относятся текстовые редакторы. Текстовый редактор-первый тип прикладной программы, который должны освоить ученики, выбор текстового редактора, используемого в учебных целях, зависит от технического и программного обеспечения школьного и компьютерного класса. При использовании IBM PC и операционной системы MS-DOS целесообразно познакомить учащихся с одним из простых текстовых редакторов (например:Norton Editor) и каким-нибудь более совершенным редактором (текстовым процессором)Лексикон, Work и др. Если в классе работает операционная система windows , то начать можно с ТР «Блокнот». Безусловно, MS Word – один из наиболее развитых ТР, в котором реализована самая современная технология обработки текста.Тем не менее MS Word –очень сложный программный продукт. За время, отведенное под данную тему учебной программы, нельзя освоить даже половину его возможностей. Многие элементы интерфейса Word оказываются невостребованными и создают определенный «информационный» шум, отвлекающий учеников. Практически все приемы работы с текстовыми редакторами, которые можно освоить в рамках базового курса, реализованы в WordPad. Интерфейс этого редактора близок к интерфейсу Word , но «без излишеств». НАЗАД.
Поиск (в широком смысле) 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
