Наложенный код - Superimposed code

Карточка с надрезом и данными для библиографического элемента. Кромки еще не надрезаны.

А наложенный код Такие как Затокодирование это своего рода хэш-код это было популярно в системы маргинальных перфокарт.

Системы маржинальных перфокарт

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

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

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

Наложенные коды

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

Кэлвин Мурс изобрел Затокодирование в M.I.T., механическая система поиска информации, основанная на наложенных кодах, и сформировала Компания Затор в 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 .[2]

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

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

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

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

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

Другие наложенные коды

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

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

Рекомендации

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

внешняя ссылка