Из Википедии, бесплатной энциклопедии
  (Перенаправлено из Затокодинга )
Перейти к навигации Перейти к поиску
Карточка с надрезом и данными для библиографического элемента. Кромки еще не надрезаны.

Накладывается код , такой как Zatocoding является своего рода хэш - кода , который был популярен в окраинных системах перфорированный-карт .

Системы маргинальных перфокарт [ править ]

Основная статья: карта с надрезом

Многие названия, некоторые из которых являются товарными знаками, использовались для систем маргинальных перфокарт: карты с краями, карты с прорезями, EZ Sort, Zatocards, McBee, McBee Keysort, Flexisort, Velom, Rocket и т. соответствующая информация - обычно имя и автор книги, исследовательской работы или журнальной статьи на ближайшей полке; а также список тем и ключевых слов. Некоторые наборы карточек содержали всю необходимую пользователю информацию на самой карточке, рукописную, машинописную или на микрофильмах ( апертурная карточка).). На каждой карточке в стопке был одинаковый набор предварительно пробитых отверстий. Пользователь мог бы найти конкретные карты, имеющие отношение к поиску, совместив отверстия в наборе карт (с помощью держателя карты или лотка для карт), вставив один или несколько стержней, похожих на вязальные иглы, на всем протяжении стопки, так что желаемый карточки (которые были надрезаны или разрезаны) выпали из несоответствующих карточек в коллекции (оставленных без надреза), которые остались на игле (ах). Пользователь может повторять этот выбор много раз, чтобы сформировать сложный логический поискзапрос. На карточке, относящейся к 2 или более предметам, будут вырезаны отверстия для каждого из этих предметов, так что эта карточка выпадет, когда будет выбран один или другой или оба предмета. Системы кодирования "наложенного кода", такие как Zatocoding, экономили место, вводя несколько или все предметы в одно поле; такой «наложенный код» хранит гораздо больше информации на меньшем пространстве, но за счет случайных «ложных» выборок. [1]

Если у вас есть коллекция учетных карточек, по одной на книгу, исследовательскую статью или журнальную статью в библиотеке, со списком ключевых слов (тем), обсуждаемых в конкретной книге, написанном на карточке этой книги, «очевидный способ» их закодировать предметов состоит в том, чтобы подсчитать общее количество предметов, используемых во всей коллекции R, сделать ряд отверстий R в верхней части каждой карточки и для каждого предмета, фактически обсуждаемого в конкретной книге, вырезать прорезь из отверстия, соответствующего этому предмет в карточке, соответствующей этой книге. [2]Естественно, для этого также требуется отдельный список каждого предмета, используемого в коллекции, который указывает, какое отверстие пробивается для каждого предмета. К сожалению, в коллекции могут быть тысячи различных предметов, и пробивать тысячи дырок в каждой карточке непрактично. Хотя может показаться невозможным использовать менее 1 отверстия на предмет, системы наложенного кода могут решить эту проблему.

Наложенные коды [ править ]

Система поиска информации Zatocoding была разработана Кальвином Мурсом в 1947 году [3].

Кэлвин Мурс изобрел Zatocoding в Массачусетском технологическом институте, механическую систему поиска информации, основанную на наложенных кодах, и основал компанию Zator в 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 слотов.

Позже, когда нам нужно найти книги по какому-то конкретному предмету, мы ищем этот предмет в нашем списке всех предметов R, находим соответствующий шаблон слотов из n слотов и вставляем n игл через всю стопку в этом шаблоне. Все карты, вырезанные по этому шаблону, выпадут. Возможно, что несколько других, нежелательных карт также могут выпасть - карты, у которых есть несколько предметов, чьи рисунки отверстий перекрываются таким образом, чтобы имитировать желаемый рисунок. Вероятность F того, что какая-то нежелательная карта с прорезанными в ней v прорезями, выпадет, когда мы выберем какой-то узор из n игл, приблизительно равна . Большинство систем имеют достаточно большое N и достаточно маленькое r, так что v <N / 2 (т. Е. Карта имеет менее половины перфорации), так что вероятность того, что нежелательная карта проваливается, меньше чем . [2]

Есть несколько способов выбрать отверстия для каждого предмета.

(Было разработано несколько вариантов затокодирования. Борн описывает вариант «для новых поисковых систем, требующих высокой производительности системы наложенного кодирования» [6], используя подход, опубликованный Муерсом в 1959 г. [7] ).

Затокодирование [ править ]

Настройка затокода для определенного списка тем R выглядит примерно так: [2]

  • Для первого предмета случайным образом выберите n из N слотов.
  • Для второго предмета выберите n из N ячеек случайным образом, но убедитесь, что этот шаблон не идентичен первому предмету.
  • ...
  • Для R-го предмета выберите n из N ячеек случайным образом, но убедитесь, что он не идентичен любому предыдущему предмету.

Другие наложенные коды [ править ]

Для затокода требуется кодовая книга, в которой перечислены все темы и случайно сгенерированный код метки, связанный с каждым из них. Другие "прямые" наложенные коды имеют фиксированную хеш-функцию для преобразования букв в (одно написание) предмета в код метки. Такие коды требуют гораздо более короткой кодовой книги, которая описывает перевод букв в слове в соответствующий код метки, и в принципе могут легко добавлять новые предметы без изменения кодовой книги. [5]

Фильтр Блума можно считать своего рода наложенного кода. [8]

Ссылки [ править ]

  1. ^ Роберт В. Уильямс.«Перфокарты: Краткое руководство» . вычисления сейчас 2002.
  2. ^ а б в г У. Росс Эшби.Журнал У. Росса Эшби: Зато-кодирование 1960 22 сентября. С. 6208-6222
  3. ^ «О обложке». Новости колледжей и исследовательских библиотек, апрель 2008 г. [1] [2]
  4. ^ Юджин Гарфилд .«Сохраняющаяся актуальность наложенного кодирования . Журнал информатики 8 (1984) 181.
  5. ^ а б Герберт Марвин Олман .«Частота письма предметного слова с приложениями к наложенному кодированию» . Труды Международной конференции по научной информации (1959).
  6. ^ Борн, Чарльз П. (1963). Методы обработки информации . John Wiley & Sons, Inc. стр. 67.
  7. ^ Mooers, Calvin Н. (апрель 1959). Применение выбора включения простого шаблона в крупномасштабные информационно-поисковые системы . Компания Затор.
  8. ^ Джеймс Бластейн; и Амаль Эль-Маазави. «Фильтры Блума - Учебное пособие, анализ и обзор» . п. 11.

Внешние ссылки [ править ]

  • Кальвин Н. Мурс. «Применение случайных кодов для сбора статистической информации» . Диссертация (MS) Массачусетский технологический институт. Кафедра математики, 1948 г.
  • Кальвин Н. Мурс. «Затокодирование применительно к механической организации знаний» . Журнал Американского общества информационных наук и технологий. 2007 г.