Накладывается код , такой как Zatocoding является своего рода хэш - кода , который был популярен в окраинных системах перфорированный-карт .
Системы маржинальных перфокарт
Многие названия, некоторые из которых являются товарными знаками, использовались для систем маргинальных перфокарт: карты с надрезом, карты с прорезями, EZ Sort, Zatocards, McBee, McBee Keysort, Flexisort, Velom, Rocket и т. Д. соответствующая информация - обычно имя и автор книги, исследовательской работы или журнальной статьи на ближайшей полке; а также список тем и ключевых слов. Некоторые наборы карточек содержали всю необходимую пользователю информацию на самой карточке, написанную от руки, машинописную или на микрофильме ( апертурная карточка ). На каждой карте в стопке был одинаковый набор предварительно пробитых отверстий. Пользователь мог бы найти конкретные карты, имеющие отношение к поиску, совместив отверстия в наборе карт (с помощью держателя карты или лотка для карт), вставив один или несколько стержней, похожих на вязальные иглы, на всем протяжении стопки, так что желаемый карты (которые были надрезаны или разрезаны) выпали из несоответствующих карт в коллекции (оставленных без надрезов), которые остались на игле (ах). Пользователь может повторять этот выбор много раз, чтобы сформировать сложный логический поисковый запрос. На карточке, относящейся к 2 или более предметам, будут вырезаны отверстия для каждого из этих предметов, так что эта карточка выпадет, когда будет выбран один или другой или оба предмета. Системы кодирования "наложенного кода", такие как Zatocoding, экономили место, вводя несколько или все предметы в одно поле; такой «наложенный код» хранит гораздо больше информации на меньшем пространстве, но за счет случайных «ложных» выборок. [1]
Если у вас есть коллекция учетных карточек, по одной на книгу, исследовательскую статью или журнальную статью в библиотеке, со списком ключевых слов (тем), обсуждаемых в конкретной книге, написанном на карточке этой книги, «очевидный способ» их закодировать предметов состоит в том, чтобы подсчитать общее количество предметов, используемых во всей коллекции R, сделать ряд отверстий R в верхней части каждой карточки и для каждого предмета, фактически обсуждаемого в конкретной книге, вырезать прорезь из отверстия, соответствующего этому предмет в карточке, соответствующей этой книге. [2] Естественно, это также требует отдельного списка каждого предмета, используемого в коллекции, который указывает, какое отверстие пробивается для каждого предмета. К сожалению, в коллекции могут быть тысячи различных предметов, и пробивать тысячи дырок в каждой карточке непрактично. Хотя может показаться невозможным использовать менее 1 отверстия для каждого объекта, системы наложенного кода могут решить эту проблему.
Наложенные коды
Система поиска информации Zatocoding была разработана Кальвином Мурсом в 1947 году [3].
Кэлвин Мурс изобрел Zatocoding в Массачусетском технологическом институте, механическую систему поиска информации, основанную на наложенных кодах, и основал Zator Company в 1947 году для коммерциализации своих приложений. [4] Конкретный наложенный код, используемый в этой системе, называется затокодированием , в то время как система поиска информации о маргинальных перфокартах в целом называется « затор ». [5]
Настройка наложенного кода для конкретной библиотеки выглядит примерно так:
- Просматривая каждую карточку в указателе, создается список всех предметов R, используемых в этой конкретной библиотеке, и отмечается максимальное количество предметов r, фактически записанных на одной карточке. (Например, предположим, что у нас есть 8000 предметов, и библиотекарь решает проиндексировать только первые r = 4 предмета в книге).
- Библиотекарь смотрит на физическую карточку с надрезом и отмечает количество отверстий N на каждой карточке. (Если N> = R, тогда мы могли бы использовать упомянутый выше «очевидный способ» - весь смысл затокодирования в том, что он работает, даже когда N намного меньше R).
- Библиотекарь выбирает некоторое количество n мест по каждому предмету - обычно [2]
- В списке всех предметов R для каждого предмета запишите, какие отверстия будут сделаны для этого предмета. Вместо того, чтобы проделывать одно отверстие для каждого объекта «очевидным способом», наложенный код будет делать n отверстий для каждого объекта. (Есть несколько способов выбрать эти шаблоны - они позволяют различать различные наложенные коды; мы обсудим их ниже).
- Когда приходит новая книга, сделайте для нее новую карточку:
- Возьмите чистую карточку со стандартными N отверстиями и напишите название книги и т. Д. Посередине.
- Запишите на карточке темы, охваченные книгой.
- Для каждого из r лучших предметов найдите этот предмет в большом списке, посмотрите, какие n ячеек нужно вырезать для этого предмета, и вырежьте их.
- Когда карта закончена, в ней может быть до r * n прорезей, но более вероятно, что по крайней мере некоторые из соответствующих шаблонов слотов перекрываются, в результате чего остается только v
Позже, когда нам нужно найти книги по какому-то конкретному предмету, мы ищем этот предмет в нашем списке всех предметов R, находим соответствующий шаблон слотов из n слотов и вставляем n игл через всю стопку в этом шаблоне. Все карты, вырезанные по этому шаблону, выпадут. Возможно, что несколько других, нежелательных карт также могут выпасть - карты, у которых есть несколько предметов, чьи рисунки отверстий перекрываются таким образом, чтобы имитировать желаемый рисунок. Вероятность F того, что какая-то нежелательная карта с прорезанными на ней v прорезями, выпадет, когда мы выберем какой-то узор из n игл, приблизительно равна. Большинство систем имеют достаточно большое N и достаточно маленькое r, так что v
Есть несколько способов выбрать отверстия для каждого предмета.
(Было разработано несколько вариантов затокодирования. Борн описывает вариант «для новых поисковых систем, требующих высокой производительности системы наложенного кодирования» [6], используя подход, опубликованный Муерсом в 1959 г. [7] ).
Затокодирование
Настройка затокода для определенного списка тем R выглядит примерно так: [2]
- Для первого предмета случайным образом выберите n из N слотов.
- Для второго предмета выберите n из N ячеек случайным образом, но убедитесь, что этот шаблон не идентичен первому предмету.
- ...
- Для R-го предмета выберите n из N ячеек случайным образом, но убедитесь, что он не идентичен любому предыдущему предмету.
Другие наложенные коды
Для затокода требуется кодовая книга, в которой перечислены все темы и случайно сгенерированный код метки, связанный с каждым из них. Другие "прямые" наложенные коды имеют фиксированную хеш-функцию для преобразования букв в (одно написание) предмета в код метки. Такие коды требуют гораздо более короткой кодовой книги, которая описывает перевод букв в слове в соответствующий код метки, и в принципе могут легко добавлять новые предметы без изменения кодовой книги. [5]
Фильтр Блума можно считать своего рода наложенного кода. [8]
Рекомендации
- ^ Роберт В. Уильямс. «Перфокарты: Краткое руководство» . вычисления сейчас 2002.
- ^ а б в г У. Росс Эшби. Журнал У. Росса Эшби: Зато-кодирование 1960 22 сентября. С. 6208-6222
- ^ «О обложке». Новости колледжей и исследовательских библиотек, апрель 2008 г. [1] [2]
- ^ Юджин Гарфилд . «Сохраняющаяся актуальность наложенного кодирования . Журнал информатики 8 (1984) 181.
- ^ а б Герберт Марвин Олман . «Частота письма предметного слова с приложениями к наложенному кодированию» . Труды Международной конференции по научной информации (1959).
- ^ Борн, Чарльз П. (1963). Методы обработки информации . John Wiley & Sons, Inc. стр. 67.
- ^ Муерс, Кальвин Н. (апрель 1959 г.). Применение выбора включения простого шаблона в крупномасштабные информационно-поисковые системы . Компания Затор.
- ^ Джеймс Бластейн; и Амаль Эль-Маазави. «Фильтры Блума - Учебное пособие, анализ и обзор» . п. 11.
Внешние ссылки
- Кальвин Н. Мурс. «Применение случайных кодов для сбора статистической информации» . Диссертация (MS) Массачусетский технологический институт. Кафедра математики, 1948 г.
- Кальвин Н. Мурс. «Затокодирование применительно к механической организации знаний» . Журнал Американского общества информационных наук и технологий. 2007 г.