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

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

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

Перфорированные системы

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

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

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

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

Кэлвин Мурс изобрел Zatocoding в Массачусетском технологическом институте, механическую систему поиска информации, основанную на наложенных кодах, и основал компанию Zator в 1947 году для коммерциализации ее приложений. ^[4] Конкретный наложенный код, используемый в этой системе, называется Zatocoding , в то время как система поиска информации с помощью перфокарт на полях в целом называется « Zator ». ^[5]

Настройка наложенного кода для конкретной библиотеки выглядит примерно так:

• Просматривая каждую карточку в индексе, создается список всех предметов R, используемых в данной конкретной библиотеке, и отмечается максимальное количество предметов r, фактически записанных на одной карточке. (Например, у нас есть 8000 предметов, и библиотекарь решает индексировать только верхние r=4 предмета на книгу).
• Библиотекарь смотрит на физическую карту с надрезами по краям и отмечает количество отверстий N в каждой карте. (Если N >= R, то мы могли бы использовать «очевидный способ», упомянутый выше — весь смысл Zatocoding в том, что он работает, даже когда N намного меньше R).
• Библиотекарь выбирает некоторое количество n слотов для каждого предмета — обычно ^[2] ${\displaystyle n=N(1-2^{-{\frac {1}{r}}})}$
• В списке всех предметов R для каждого предмета запишите, какие отверстия будут прорезаны для этого предмета. Вместо того, чтобы прорезать одно отверстие для предмета "очевидным образом", суперналоженный код прорежет n отверстий для предмета. (Существует несколько способов выбрать эти шаблоны — они различают различные суперналоженные коды; мы обсудим их ниже).
• Когда поступит новая книга, сделайте для нее новую карточку:
  • Возьмите чистую карточку со стандартными N отверстиями и напишите в середине название книги и т. д.
  • Запишите на карточке темы, о которых идет речь в книге.
  • Для каждого из r основных предметов найдите этот предмет в большом списке и посмотрите, какие n слотов для этого предмета следует сократить, а затем сократите их.
  • Когда карта будет готова, на ней может быть вырезано до r*n слотов, но более вероятно, что по крайней мере некоторые из шаблонов слотов перекрываются, в результате чего остается всего v < r*n слотов.

Позже, когда нам нужно найти книги по какой-то конкретной теме, мы ищем эту тему в нашем списке всех R тем, находим соответствующую схему прорезей из n прорезей и прокладываем n игл по всей стопке в этой схеме. Все карты, вырезанные по этой схеме, выпадут. Возможно, что также выпадут несколько других нежелательных карт — карты с несколькими темами, схемы отверстий которых перекрываются таким образом, чтобы имитировать желаемую схему. Вероятность F того, что некоторая нежелательная карта с v прорезями в ней провалится, когда мы выбираем некоторую схему из n игл, составляет приблизительно . Большинство систем имеют достаточно большое N и достаточно малое r, так что v < N/2 (т. е. карта пробита менее чем наполовину), так что вероятность проваливания нежелательной карты меньше . ^[2] ${\displaystyle F=\left({\frac {v}{N}}\right)^{n}}$ ${\displaystyle F<\left({\frac {1}{2}}\right)^{n}}$

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

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

Zatocode

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

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

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

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

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

Ссылки

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

Внешние ссылки

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