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

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

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

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

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

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

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

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

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

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

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

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

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

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

Настройка Zatocode для определенного списка предметов 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.

[1] Роберт В. Уильямс. «Перфокарты: Краткий урок» .компьютеры сейчас 2002.

[ashby-2] Перейти обратно: ^а ^б ^с ^д У. Росс Эшби. Журнал У. Росса Эшби: Зато-кодирование 1960, 22 сентября. с. 6208-6222

[3] «О обложке».Новости колледжей и научных библиотек, апрель 2008 г. [1] [2]

[4] Юджин Гарфилд . «Постоянная актуальность наложенного кодирования .Журнал информатики 8 (1984) 181.

[ohlman-5] Перейти обратно: ^а ^б Герберт Марвин Олман . «Частота букв предметного слова с применением к наложенному кодированию» .Материалы Международной конференции по научной информации (1959).

[6] Борн, Чарльз П. (1963). Методы обработки информации . John Wiley & Sons, Inc. с. 67.

[7] Мурс, Кэлвин Н. (апрель 1959 г.). Применение простого выбора включения шаблона в крупномасштабных системах поиска информации . Компания Затор.

[8] Джеймс Блюстейн; и Амаль Эль-Маазави. «Фильтры Блума — учебное пособие, анализ и обзор» .п. 11.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]