Планирование материальных потребностей

MRP
MRP (Material Requirement Planning — Планирование материальных потребностей). Компьютерная методология, используемая в управлении производством, для планирования производства и запасов.
Основными целями MRP систем являются:
• удовлетворение потребности в материалах, компонентах и продукции для планирования производства и доставки потребителям;
• поддержка низких уровней запасов;
• планирование производственных операций, расписаний доставки, закупочных операций.
Алгоритм работы
Для работы MRP-модуля требуются следующие входные данные:
• Основной производственный план (MPS);
• Список номенклатуры (IM);
• Данные о состоянии запасов (книга учета запасов). В этом документе отражаются вся наличествующая номенклатура: запасы, незавершенное производство, полуфабрикаты, готовая продукция.
• Спецификация состава изделия (BOM)
Результатами работы MRP-модуля являются следующие документы.
• График заказов на закупку/производство материалов и комплектующих (Planned Order Schedule) - документ, расписывающий какое количество сырья, материалов, комплектующих должно быть заказано в каждый плановый период в течение срока планирования. Этот документ определяет внутрипроизводственный план сборки комплектующих и план внешних закупок.
• Изменения к графику заказов на закупку/производство материалов и комплектующих (Changes in planned orders) - документ, содержащий корректировки ранее спланированных заказов на закупку/производство материалов и комплектующих.
Основные элементы компьютерных MRP - систем.
Введение
Новая экономическая ситуация ставит перед предприятиями ряд задач, которые ранее ими не рассматривались. Среди наиболее важных задач, стоящих перед промышленными предприятиями в современных условиях, можно выделить:
• повышение конкурентной борьбы,
• требование выпускать продукцию в соответствии с текущими заказами покупателей, а не с долгосрочными перспективными планами,
• необходимость оперативного принятия решений в сложной экономической ситуации,
• укрепление связей между поставщиками, производителями и покупателями.
В конкурентной борьбе побеждает только тот, кто быстрее других реагирует на изменения в бизнесе и принимает более верные решения. Именно информационные технологии помогают руководителям промышленных предприятий в решении этих сложных задач. Страны рыночной экономики имеют большой опыт создания и развития информационных технологий для промышленных предприятий. Одним из наиболее распространенных методов управления производством и дистрибуции в мире является стандарт MRP II (Manufacturing Resourse Planning), разработанный в США и поддерживаемый американским обществом по контролю за производством и запасами - American Production and Inventory Control Society (APICS). APICS регулярно издает документ "MRP II Standart System", в котором описываются основные требования к информационным производственным системам. Последнее издание этой системы промышленных стандартов вышло в 1989 г.
MRP II – это набор проверенных на практике разумных принципов, моделей и процедур управления и контроля, служащих повышению показателей экономической деятельности предприятия. Идея MRP II опирается на несколько простых принципов, например, разделение спроса на зависимый и независимый. MRP II Standart System содержит описание 16 групп функций системы:
1. Sales and Operation Planning (Планирование продаж и производства).
2. Demand Management (Управление спросом).
3. Master Production Scheduling (Составление плана производства).
4. Material Requirement Planning (Планирование материальных потребностей).
5. Bill of Materials (Спецификации продуктов).
6. Inventory Transaction Subsystem (Управление складом).
7. Scheduled Receipts Subsystem (Плановые поставки).
8. Shop Flow Control (Управление на уровне производственного цеха).
9. Capacity Requirement Planning (Планирование производственных мощностей).
10. Input/output control (Контроль входа/выхода).
11. Purchasing (Материально техническое снабжение).
12. Distribution Resourse Planning (Планирование ресурсов распределения).
13. Tooling Planning and Control ( Планирование и контроль производственных операций).
14. Financial Planning (Управление финансами).
15. Simulation (Моделирование).
16. Performance Measurement (Оценка результатов деятельности).
С накоплением опыта моделирования производственных и непроизводственных операций эти понятия постоянно уточняются, постепенно охватывая все больше функций.
В своем развитии стандарт MRP II прошел несколько этапов развития:
• 60-70 годах - планирование потребностей в материалах, на основании данных о запасах на складе и состава изделий, (Material Requierment Planning)
• 70-80 годы - планирование потребностей в материалах по замкнутому циклу (Cloosed Loop Material Requirment Planning), включающее составление производственной программы и ее контроль на цеховом уровне,
• конец 80-90-е - на основе данных, полученных от поставщиков и потребителей, ведение прогнозирования, планирования и контроля за производством,
• 90-е - планирование потребностей в распределении и ресурсах на уровне предприятия - Enterprise Resourse Planning и Distributed Requirements Planning.
Задачей информационных систем класса MRP II является оптимальное формирование потока материалов (сырья), полуфабрикатов (в том числе находящихся в производстве) и готовых изделий. Система класса MRP II - имеет целью интеграцию всех основных процессов, реализуемых предприятием, таких как снабжение, запасы, производство, продажа и дистрибьюция, планирование, контроль за выполнением плана, затраты, финансы, основные средства и т.д.
Стандарт MRP II делит сферы отдельных функций (процедур) на два уровня: необходимый и опциональный. Для того, чтобы программное обеспечение было отнесено к классу MRP II, оно должно выполнять определенный объем необходимых (основных) функций (процедур). Некоторые поставщики ПО приняли различный диапазон реализаций опциональной части процедур этого стандарта.
Результаты использования интегрированных систем стандарта MRP II:
• получение оперативной информации о текущих результатах деятельности предприятия как в целом, так и с полной детализацией по отдельным заказам, видам ресурсов, выполнению планов;
• долгосрочное, оперативное и детальное планирование деятельности предприятия с возможностью корректировки плановых данных на основе оперативной информации;
• решение задач оптимизации производственных и материальных потоков;
• реальное сокращение материальных ресурсов на складах;
• планирование и контроль за всем циклом производства с возможностью влияния на него в целях достижения оптимальной эффективности в использовании производственных мощностей, всех видов ресурсов и удовлетворения потребностей заказчиков;
• автоматизация работ договорного отдела с полным контролем за платежами, отгрузкой продукции и сроками выполнения договорных обязательств;
• финансовое отражение деятельности предприятия в целом;
• значительное сокращение непроизводственных затрат;
• защита инвестиций, произведенных в информационные технологии;
• возможность поэтапного внедрения системы, с учетом инвестиционной политики конкретного предприятия.
В основу MRP II положена иерархия планов. Планы нижних уровней зависят от планов более высоких уровней, т.е. план высшего уровня предоставляет входные данные, намечаемые показатели и/или какие-то ограничительные рамки для планов низшего уровня. Кроме того эти планы связаны между собой таким образом, что результаты планов нижнего уровня оказывают обратное воздействие на планы высшего уровня.

Если результаты плана нереалистичны, то этот план или планы высшего уровня должны быть пересмотрены. Таким образом можно проводить координацию спроса и предложения ресурсов на определенном уровне планирования и ресурсов на высших уровнях планирования.
СТРАТЕГИЧЕСКОЕ ПЛАНИРОВАНИЕ
Стратегическое планирование – это долгосрочное планирование. Оно обычно составляется на срок от одного до пяти лет. Оно основано на макроэкономических показателях, таких как тенденции развития экономики, изменение технологий, состояние рынка и конкуренции. Стратегическое планирование обычно распространяется на каждый год пятилетки и представляет собой плановые показатели (цели) высшего уровня.
БИЗНЕС-ПЛАНИРОВАНИЕ
Бизнес-план – это обычно план на год, который также составляется на ежегодной основе. Иногда он неоднократно пересматривается в течение года. Как правило он является результатом совещания управленческого состава, на котором сводятся планы продаж, инвестиций, развития основных средств и потребности в капитале и бюджетирование. Эта информация подается в денежном выражении. Бизнес-план определяет плановые показатели по объемам продаж и производства, а также другие планы низшего уровня.
ПЛАНИРОВАНИЕ ОБЪЕМОВ ПРОДАЖ И ПРОИЗВОДСТВА
Если бизнес-план предоставляет итоговые данные по объемам продаж помесячно (в денежном выражении), то план объемов продаж и производства разбивает эту информацию по 10-15 ассортиментным группам. В результате получают план производства, который ежемесячно пересматривается, принимая во внимание план предыдущего месяца, реальные результаты и данные бизнес-плана.
План объемов продаж и производства обычно включает следующие элементы:
• Объем продаж
• Производство
• Запасы
• Незавершенный объем производства
• Отгрузка
Из этих элементов Объем Продаж и Отгрузка - это прогнозы, т.к. это внешние данные, которые прямому контролю не поддаются. Объем производства планируется, это внутренний показатель, поддающийся прямому контролю. Планы по объемам запасов и незавершенным объемам производства контролируются косвенно, манипулируя данными прогнозов объема продаж, прогнозов объема отгрузки и/или плана объемов производства.
Объемы запасов и незавершенки управляются по-разному, в зависимости от типов продукции, выпускаемой или продаваемой компанией. Плановый объем запасов - это важный фактор, особенно для тех компаний, которые производят продукцию на склад. Плановый объем незавершенки является важным фактором для тех компаний, которые производят продукцию на заказ.
Фокусом планирования объема продаж и производства является план производства. Хотя он и называется планом производства, это в принципе не просто план выпуска продукции. Он требует наличие необходимого объема ресурсов по всей компании в целом. Если отдел маркетинга планирует скачок в продажах определенного ассортимента продуктов, инженеры должны обеспечить наличие необходимого объема оборудования; отдел МТС должен будет обеспечить дополнительные поставки материалов (наличие новых поставщиков); отдел кадров должен будет обеспечить наличие дополнительного объема трудовых ресурсов, а также организовать новые рабочие смены. Плюс ко всему необходимо будет обеспечить наличие необходимого объема капитала (для оплаты дополнительного объема ресурсов и запасов).
ПЛАНИРОВАНИЕ РЕСУРСОВ
План производства будет нереален, если не будет обеспеченно наличие необходимого объема ресурсов. Планирование ресурсов - это долгосрочное планирование, которое позволяет оценить необходимый (для выполнения плана производства) и наличный объем ключевых ресурсов, таких как люди, оборудование, здания и сооружения. Если возникнет потребность в наличии необходимого объема дополнительных ресурсов, то, возможно, потребуется пересмотреть бизнес-план.
Планирование ресурсов затрагивает только ключевые ресурсы и составляется на срок действия плана по производству (обычно один год). Ресурс может считаться ключевым, если его стоимость достаточно велика, или если срок его поставки достаточно велик или если от него зависят другие ресурсы. Ресурсы могут быть как внешними (возможности поставщиков), так и внутренними (оборудование, складские площади, деньги).
ГЛАВНЫЙ ПЛАН-ГРАФИК ПРОИЗВОДСТВА (ГПГП)
Роль начальника отдела планирования - перевод производственного плана в специфичный план-график производства. Этот план - ГПГП - план производства, наложенный на шкалу времени. ГПГП показывает что будет производиться, когда и в каких объемах.
Т.к. производственный план выражен в таких единицах как рубли, часы, тонны, то для того, чтобы получить ГПГП, необходимо произвести некоторые шаги по трансформации производственного плана. Плановые объемные показатели по ассортиментной группе необходимо перевести в плановые объемы и сроки по каждому продукту этой группы в раздельности. В зависимости от типа и объема выпускаемой продукции ГПГП можно разбить на недельные, дневные и даже сменные планы.
Одна из основных целей ГПГП - это обеспечение буфера: ГПГП отличает прогнозы и потребности отдела сбыта от MRP (планирование потребностей в материалах). Философия такова: прогнозы и заказы на продажу (заказы клиентов) выражают спрос (или отгрузку), в то время как ГПГП отображает то, что реально будет произведено в соответствии с имеющимся спросом. В соответствии с ГПГП возможно производство продукции в период, когда спрос на нее невысок, и наоборот. Это может иметь место при производстве продукции, спрос на которую сезонен.
СПРОС ГПГП
Начальник отдела планирования должен принимать во внимание все источники независимого спроса. Независимый спрос - это спрос, который может быть прогнозом, обычно это спрос на готовую продукцию и запчасти. Он в корне отличается от зависимого спроса (спрос, который можно рассчитать, исходя из данных по составу изделия). Источники независимого спроса: производственный план, прогнозируемый объем отгрузки, заказы клиентов (при производстве или сборке под заказ), спрос на запчасти, межзаводской спрос и страховой запас.
Основная проблема в составлении ГПГП - это определение того, планирование по каким изделиям/комплектующим должно вестись отделом планирования, а по каким должно вестись автоматически (системой MRP). Изделия, планируемые отделом планирования, - это те изделия, планирование которых должно вестись под контролем людей. Изделия, планируемые системой MRP, т.е. автоматически, не требуют такой степени контроля (они зависят от ГПГП). Определение того, как должно вестись планирование того или иного вида изделия зависит от типов изделий и технологических процессов. Обычно очень маленькое количество изделий должны контролироваться отделом планирования.
ОБЩЕЕ ПЛАНИРОВАНИЕ МОЩНОСТЕЙ
Как и планирование ресурсов, общее планирование мощностей является долгосрочным и ведется по ключевым ресурсам. Этот процесс использует данные ГПГП, а не данные производственного плана. Так если ГПГП выражен в объемных и временных характеристиках, то общее планирование мощностей используется для создания более детализированного плана, который может быть очень полезен при оценке средних потребностей компании в целом, а также для оценки ГПГП.
MRP ИЛИ ПЛАНИРОВАНИЕ ПОТРЕБНОСТЕЙ В МАТЕРИАЛАХ
Исторически MRP (планирование потребностей материалов) предназначалось для контроля за запасами и их пополнения. В рамках MRP II (планирование ресурсов предприятия) его использование было расширено до планирования потребностей в мощностях, проведения приоритезации и до замыкания всей цепочки планирования.
MRP отвечает на четыре основных вопроса:
• Что мы собираемся производить?
• Что нам для этого необходимо?
• Чем мы уже располагаем?
• Что нам необходимо дополучить?
ГПГП отвечает на первый вопрос "Что мы собираемся произвести?". В целях достижения целей, поставленных ГПГП, ведется планирование всей производственной и дистрибуторской деятельности. Т.к. ГПГП - это график, то он также отвечает и на такие вопросы как "Сколько" и "Когда".
Второй вопрос "Что нам для этого необходимо?" по сути спрашивает: "Какие изделия/комплектующие нам нужно произвести (или закупить), чтобы выполнить планы ГПГП?". Чтобы ответить на этот вопрос, нам нужно знать две вещи: ГПГП и правильные данные о составе изделия (структуре продукта, формуле продукта). ГПГП и данные о составе изделия позволяют системе определить Что, Сколько и Когда потребуется для того, чтобы произвести то, что нам нужно.
Вопрос "Чем мы уже располагаем?" можно разделить на два вопроса: "Что у нас уже есть на руках?" и "Что мы ожидаем по заказам?". Наличный запас на складе - это ответ на первый вопрос, а плановый объем поступлений продукции с производства и от поставщиков - это ответ на второй вопрос. Все вместе эти данные не только дают информацию о наличном объеме запасов, но они также позволяют системе оценить ожидаемый объем запаса. Чтобы ответить на последний вопрос, нужно знать ответы на три предыдущих. Взяв то, что нужно произвести (брутто-потребности), отняв то, что уже есть (на складе и плановые поступления), мы узнаем то, что нам нужно дополучить (нетто-потребности).
CRP ИЛИ ПЛАНИРОВАНИЕ ПОТРЕБНОСТЕЙ В МОЩНОСТЯХ
Но наличие необходимого объема необходимых материалов ничего не значит без наличия достаточного свободного объема рабочего времени. CRP (или планирование потребностей в мощностях) - это планирование среднего уровня, которое использует данные запланированных MRP заказов и заказов на производство для определения необходимого объема рабочего времени (как по трудовым, так и по техническим ресурсам).
Планирование ресурсов и общее планирование мощностей - это планирование высшего уровня, используемое для планирования таких ресурсов как физическое оборудование. CRP является более детализированным планированием. Загрузка рабочих мест рассчитывается на основе технологического маршрута изготовления продукта, который определяет, каким именно образом производится данный вид продукта. Технологический маршрут похож на инструкцию к применению - набор шагов (или техопераций), которые необходимо совершить для изготовления чего-то. Каждая техоперация совершается на каком-то рабочем месте, которое может состоять из одного или нескольких человек и/или оборудования.
DRP ИЛИ ПЛАНИРОВАНИЕ ПОТРЕБНОСТЕЙ В РАСПРЕДЕЛЕНИИ
Когда какие-то материалы передвигаются от поставщика к потребителю, они передвигаются по цепи поставок (или рыночному каналу). Если представить это графически, то цепь поставок представляет собой потоки спроса и предложения между поставщиками и какими-то подразделениями компании Заказчика, между этими подразделениями и клиентами или между различными подразделениями одной компании. DRP (планирование потребностей в распределении) координирует спрос, предложение и ресурсы между подразделениями одной или нескольких компаний.

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

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

И третий пример: компания имеет производственные мощности в двух городах.

________________________________________
При планировании спроса и предложения материалов между подразделениями отвечают на три основных вопроса:
• Что нам нужно получить (с других подразделений)?
• Что мы собираемся поставить (другим подразделениям)?
• Что мы можем поставить?
Хотя эти вопросы и похожи на вопросы, задаваемые MRP (планирование потребностей в материалах), однако существует одно принципиальное отличие. В MRP достаточно знать Какой и Когда ожидается спрос и предложение. Когда же существует несколько подразделений, между которыми постоянно передвигается продукция, тогда DRP необходимо знать плюс ко всему где (каким подразделением) возник спрос/предложение.
Ответ на вопрос "Что нам нужно получить?" создает спрос на материалы, которые необходимо поставить с другого подразделения. DRP рассчитывает полностью все эти потребности (после запуска MRP).
На вопрос "Что мы собираемся поставить?" ответ возникает при оценке всех источников спроса на продукт, включая заказы клиентов, прогноз отгрузок, потребности в запчастях, страховой запас и межзаводской спрос.
Используя данные по межзаводским запросам и заказам на распределение, между подразделениями ведется контроль спроса и предложения. На основе данных о потребностях подразделения на материалы, поставляемые другим подразделением, DRP создает запросы между этими подразделениями.
Ответ на последний вопрос "Что мы можем поставить" зависит от наличия материалов (предложение) и транспорта (ресурсов). Если спрос (потребности) превышает предложение, DRP можно использовать для закрепления материалов за несколькими подразделениями в указанной пропорции.
MRP (Material Requirements Planning)
Планирование потребности в материалах.
Главной задачей MRP является то, чтобы каждый элемент производства, каждая комплектующая деталь были в нужное время в нужном количестве. Это обеспечивается формированием такой последовательности производственных операций, которая позволяет соотносить своевременное изготовление продукции с заложенным планом выпуска. В упрощённом виде исходную информацию для MRP-системы представляют MPS, ведомость материалов, состав изделия, состояние запасов. На основании входных данных MRP-система выполняет следующие основные операции:
по данным MPS определяется количество конечных изделий для каждого периода времени планирования;
к составу конечных изделий добавляются запасные части, не включённые в MPS;
для MPS и запасных частей определяется общая потребность в материальных ресурсах в соответствии с ведомостью материалов и составом изделия с распределением по периодам времени планирования;
общая потребность материалов корректируется с учётом состояния запасов для каждого периода времени планирования;
осуществляется формирование заказов на пополнение запасов с учётом необходимого времени опережения.

Результатом работы MRP-системы является план-график снабжения материальными ресурсами производства (потребность каждой учётной единицы материалов и комплектующих для каждого периода времени). Для реализации план-графика снабжения система создаёт график заказов в привязке к периодам времени. Он используется для размещения заказов поставщикам материалов и комплектующих или для планирования самостоятельного изготовления с возможностью внесения корректировок в процессе производства. Системы класса MRP по соотношению цена/качество подходят для небольших предприятий, где функции управления ограничиваются учётом (бухгалтерским, складским, оперативным), управлением запасами на складах и управлением кадрами.
Д.А. Гаврилов "Управление производством на основе стандарта MRP II" - СПб: Питер, 2003
MRP II (Manufacturing Resource Planning)
Планирование производственных ресурсов. Методология MRP II имеет целью планирование всех ресурсов предприятия для реализации производственного плана: материалов, мощностей и финансовых средств.

Программный продукт класса MRP II, согласно стандартам, утвержденным APICS (American Production and Inventory Control Society) включает следующие 16 функций:
1. Sales and Operation Planning -- планирование продаж и производства;
2. Demand Management -- управление спросом;
3. Master Production Scheduling -- составление плана производства;
4. Material Requirement Planning -- планирование потребностей в сырье и материалах;
5. Bill of Materials -- спецификации продукции;
6. Inventory Transaction Subsystem -- складская подсистема;
7. Scheduled Receipts Subsystem -- отгрузка готовой продукции;
8. Shop Flow Control -- управление производством на цеховом уровне;
9. Capacity Requirement Planning -- планирование производственных мощностей;
10. Input/output control -- контроль входа/выхода;
11. Purchasing -- материально-техническое снабжение;
12. Distribution Resource Planning -- планирование запасов сбытовой сети;
13. Tooling Planning and Control -- планирование и управление инструментальными средствами;
14. Financial Planning -- финансовое планирование;
15. Simulation -- моделирование;
16. Performance Measurement -- оценка результатов деятельности.


Игра stalker перевернула все представления об отечественной игровой индустрии. Этот игровой шедевр должен увидеть каждый!

кредитование

Компьютеры Apple - стандарт, к которому хочется стремится.

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

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

В настоящее время проблема автоматического определения языка текстовых документов являет-ся весьма актуальной для задач, связанных с обработкой больших объемов информации. Например, в системах тематического сбора информации в Интернет необходимо проводить автоматическую фильтрацию (классификацию) входного потока документов, которые могут быть представлены на самых разных языках.
Для решения данной проблемы могут использоваться различные лингвистические, математиче-ские (статистические) методы или системы искусственного интеллекта. В данной статье рассматри-вается алгоритм автоматического определения языка текста, использующий смешанный подход, сочетающий методы инженерного анализа с относительной энтропией языка текста.
Энтропию языка текста можно определить как численную меру гибкости языка, которая отра-жает количество возможных вариантов текста с учётом вероятностей этих вариантов [1]. Согласно А. Н. Колмогорову, энтропия любого языка складывается из двух величин: смысловой емкости, т. е. способности языка передать некоторую смысловую информацию в тексте определенной длины, и гибкости языка, т. е. возможности одну и ту же информацию передать несколькими различными способами. Понятно, что для научно технических и художественных текстов в рамках одного языка эти составляющие будут различны.
А. Н. Колмогоров ввел определение энтропии через понятие относительной сложности. «Отно-сительной сложностью объекта y при заданном x будем считать минимальную длину l(p) програм-мы p для получения y из x» [2]. Применительно к текстовой информации можно сказать, что слож-ность текста А определяется длиной (в двоичном алфавите) минимальной программы, которая вы-водит A, а энтропия A – это её сложность, делённая на длину A в битах. Конечно, вычислить энтро-пию произвольного текста через относительную сложность (по Колмогорову) практически невоз-можно. В то же время существует целый класс программ, которые «получают» текст y из x – это программы архиваторы. Текст, сжатый, например, программой zip, является, по сути, некоторой программой, которая интерпретируется программой unzip таким образом, что на выходе получается исходный текст.
Если теперь принять, что размер сжатого текста характеризует его энтропию, то можно вычис-лить энтропию текста А по отношению к тексту В, или относительную энтропию H(В|А) [3]. Для этого необходимо сжать текст A и определить длину L(A) получившегося архива, а затем сжать конкатенацию текстов A и B и для этого архива определить длину L(A+B). Тогда оценить относи-тельную энтропию текстов А и В можно по формуле:
H(B | A) = L(A+B) – L(В).
Рассмотрим вкратце принцип работы программ архиваторов на примере популярного алгоритма сжатия LZ77 (Лемпеля Зива).
Общий принцип архивирования заключается в кодировании частых последовательностей сим-волов наименьшим количеством байт, а редких последовательностей – большим. Основу алгоритма LZ77 составляет так называемое «скользящее окно» фиксированного размера, которое представля-ет собой ранее обработанные данные. Окно размером N байт, по сути, является N байтами инфор-мации от текущей позиции сжатия обратно к началу потока. По ходу процесса сжатия ок-но перемещается («скользит») вслед за указателем текущей позиции в сжимаемом потоке данных. Принцип кодирования заключатся в том, что алгоритм ищет наибольшее совпадение следующих обрабатываемых данных с данными в скользящем окне. При нахождении таковых в выходной поток добавляется не сама последовательность символов, а ее смещение от начала буфера и количество совпавших символов. В случае если хотя бы один символ обрабатываемой последовательности не найден в окне, в выходной поток добавляется код первого несовпавшего символа. В этом случае смещение и количество символов будут записаны как последовательность 0:0, после которой следу-ет код ненайденного символа. На подобном принципе построены и другие алгоритмы сжатия тек-ста.
Анализ принципов работы алгоритмов сжатия показывает, что чем больше в сжимаемом тексте повторяющихся последовательностей символов, тем меньше будет длина архивированного файла. И, соответственно, значение относительной энтропии текстов А и В будет тем меньше, чем более «похожи» эти тексты в смысле последовательностей символов. Понятно, что относительная энтро-пия двух текстов на одном языке будет меньше относительной энтропии текстов на разных языках, поскольку в любом языке имеется характерный для этого языка набор символов и их сочетаний.
Впервые на это свойство сжатых текстов обратили внимание итальянские ученые Д. Бенедетто, Э. Кальоти и В. Лорето. Они провели ряд экспериментов и установили, что с помощью обычных программ архиваторов можно успешно проводить анализ текстов для целого класса лингвистиче-ских задач, таких как определение языка, авторства или тематики документов [4].
Теперь рассмотрим, каким образом можно практически реализовать задачу автоматического оп-ределения языка на основе понятия относительной энтропии. В первую очередь, необходимо соз-дать набор текстов образцов на всех языках, предполагаемых для анализа. Данные тексты должны быть преобразованы к набору символов Unicode. Каждый символ в таком представлении определя-ется двумя байтами и позволяет кодировать до 65 000 различных символов. В набор Unicode в на-стоящее время входят наборы символов национальных алфавитов для представления текстов на большинстве наиболее распространенных языков.
От качества текстов образцов во многом зависит точность определения языка. Данные тексты должны содержать по возможности полный набор символов языка, а также наиболее распростра-ненные в этом языке частицы, предлоги и т. д. Кроме этого, точность зависит от длины тек-стов образцов и длины определяемого текста. Очевидно, что чем больше будут длины тек-стов образцов, тем выше будет вероятность определения, но тем больше будет время определения. С другой стороны, если брать относительно небольшие фрагменты текстов, то алгоритм будет рабо-тать достаточно быстро, но в этом случае уменьшается вероятность правильного определения язы-ка. При этом, как правило, длина определяемого текста намного меньше длины текста образца.
Таким образом, для автоматического определения языка входного текста Т относительно набора текстов образцов Si (i = 1….n) необходимо выполнить следующее:
1. Преобразовать текст Т в кодировку Unicode.
2. Для каждого Si определить его относительную энтропию с текстом Т.
3. Найти Si, для которого относительная энтропия с Т минимальна. Язык данного текста образца будет соответствовать языку документа Т.
Количество операций в данном алгоритме можно сократить, а быстродействие повысить, если заранее вычислить и сохранить размеры сжатых текстов образцов.
Очевидно, что при большом количестве потенциально возможных языков время работы данного алгоритма будет достаточно большим, поскольку алгоритм предполагает последовательную конка-тенацию входного текста с каждым текстом образцом.
Для увеличения производительности алгоритма предлагается использовать следующее инженер-ное (программное) решение. Поскольку тексты представляются с помощью набора символов Uni-code, то перед сжатием можно произвести предварительное определение языковой группы, исполь-зуя знания о распределении кодов национальных символов по диапазону Unicode.
В Unicode кодировка организована не по языкам, а по скриптам. Если несколько языков исполь-зуют близкие наборы знаков, набор символов, достаточный для этой группы идентифицируется как один набор. К примеру, латинский набор содержит все знаки, используемые в английском, фран-цузском, испанском, немецком и близких языках. Каждому набору символов соответствует свой диапазон кодов, например, для кириллических символов, которые используются в русском, бело-русском, болгарском и т.п. языках, выделен диапазон [0x0400, 0x052F]. Для греческого языка опре-делены диапазоны [0x0370, 0x03FF] и [0x1F00, 0x1FFF], а для иврита – [0x0590, 0x05FF] и [0xFB00, 0xFB4F]. Таким образом, предварительно определив языковую группу анализируемого текста по кодам используемых в тексте символов, можно значительно сократить количество итераций алго-ритма определения языка. В некоторых случаях, например, для греческого, китайского, японского язык текста может быть однозначно установлен по одному только диапазону символов. С помощью разработанной авторами программы автоматического определения языка текста (свидетельство об официальной регистрации программ для ЭВМ № 2005611324) было проведено экспериментальное подтверждение эффективности предложенного метода. Эксперименты проводились для набора из 67 наиболее распространенных языков, при этом тексты образцы выбирались достаточно случай-ным образом без какой либо лингвистической проработки. Среднее время определения языка текста составило от 1 сек. (для документов, содержащих около 2000 слов), до 6 сек. (для документов, со-держащих около 150 000 слов). Для европейских языков, использующих латиницу и кириллицу, точность определения оказалась достаточно высокой – порядка 90%. При этом ошибки определения наблюдались в основном для родственных языков: так датские тексты были определены как нор-вежские, один из двух текстов на ирландском определен как английский, некоторые испанские оп-ределены как португальские, а один из сербских как боснийский. По группе арабских, кавказских и юго восточных языков выборка была менее представительна, чем по европейским, и охватила 18 языков. При проведении эксперимента не учитывался кодовый диапазон символов, тем не менее, точность определения оказалась около 70%. Больше всего ошибок наблюдалось при определении вьетнамского и грузинского языков.
Отметим еще одну особенность рассмотренного в данной статье метода – относительную про-стоту и скорость добавления новых языков для анализа. В системах, основанных на обучении, таких как метод опорных векторов (SVM) или системы искусственного интеллекта, при добавлении ново-го языка необходимо заново проводить обучение всей системы, что может занять достаточно много времени. В рассмотренном методе добавление нового языка заключается в добавлении нового тек-ста образца и весь процесс занимает не более двух минут.
Таким образом, проведенные эксперименты показывают эффективность применения свойств от-носительной энтропии и особенностей кодировки Unicode для определения языка текста не только в исследовательских целях, но и в реально действующих системах автоматической классификации документов.


Свои услуги предлагает Свадебный фотограф - самый светлый миг вашей жизни будет запечатлен на пленке настоящим профессионалом своего дела.

С теннисными пушками lobster можно играть в теннис на даче. Тренируйтесь везде, где вам удобно это делать!

Интересный и познавательный блог про СЕО: http://shakin.ru/. Все что нужно знать для успешного продвижения сайтов я нашел именно там.