Способ представления числовых ключей для обратного поискового индекса

Числа — совершенно особенная категория текстовых объектов. Они могут быть представлены разными способами: от зачастую многословного и не всегда согласованного между собой ряда убывающих числительных до записи арабскими или римскими цифрами, с разбивкой запятыми или точками, с пробелами или без них.

Не проще обстоят дела и с программным представлением таких объектов.

Привет! Меня зовут Андрей Коваленко (Keva), я занимаюсь лингвистическими задачами и делаю поисковые движки. В МойОфис возглавляю разработку корпоративного полнотекстового поиска.

Существует две основные проблемы поиска численных значений в текстовых массивах (и массивах текстов).

Первая из них — многообразие способов представления одного и того же значения в тексте. Для одного и того же числа это может быть и 3600, и 3,600, и 3.6*10^3, и просто "три тысячи шестьсот". Решается это аккуратным прописыванием способов выделения таких объектов из текста.

Вторая проблема связана с поиском числовых интервалов.

Напомню, что, как правило, поисковые системы работают с так называемым обратным индексом, отличной метафорой которого будет алфавитный указатель в конце книги: все использованные термины приведены в нормальной форме и упорядочены лексикографически — проще говоря, по алфавиту, и после каждого указан номер страницы, на которой этот термин встречается. Разница только в том, что такая координатная информация в поисковиках, как правило, значительно подробнее. Например, корпоративный поиск МойОфис (рабочее название — baalbek), для каждого появления слова в документе хранит, кроме порядкового номера, ещё и его грамматическую форму и привязку к разметке.

Поиск начинается с выбора нужного ключа в оглавлении индекса (алфавитном указателе), далее задача сводится к обработке обычного однословного запроса.

И вот этот выбор ключа или ключей для некоторого искомого интервала — например, "значение в поле 'Цена' не более 160" или "рабочий объём не менее 2500" — и становится сложной задачей.

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

Очевидно, что текстовое представление таким свойством не обладает: "2" будет больше "10". Стандартная форма также не годится: "7e3" меньше "8.1e-3". Нужна запись вида "P|M", где P — показатель степени, | — разделитель, а M — мантисса.

Примеры из предыдущего абзаца будут записаны как "+0|2", "+1|1", "+3|7" и "-3|81". Здесь все сравнения становятся уже правильными. Выборка ключей для поиска цены из примера выше будет выглядеть как проход по численным ключам индекса до тех пор, пока результат их сравнения со строкой "+2|16" меньше либо равен нулю.

Задача решена? Ну, почти. Привыкнуть к такому формату чисел ещё как-то можно. Если бы не было отрицательных чисел. Потому что -0.7 больше, чем -0.8. И даже если записать их в форме "P|M", то получатся "--1|7" и "--1|8", и результат лексикографического сравнения будет обратным численному, потому что '8' > '7'.

Что ж, заменим для отрицательных чисел значения на их дополнения до базы системы исчисления, в нашем случае до 10: "--9|3" и "--9|2". Ура? Первое больше второго? Ага. Ну и заодно, наконец, достигнута полная нечитаемость.

Давайте тогда не будем цепляться за ascii-представление и закодируем числа так, чтобы это было однозначно, компактно, и удовлетворяло требованию лексикографических сравнений.

Для удобства вычислений возьмём базу 16 (деление на 16 — это битовый сдвиг вправо на 4). Сначала приведём число к стандартному виду по основанию 16: целая часть — число от 1 до 15, показатель шестнадцатеричной степени, и дробная часть.

Значение показателя степени запишем по принципу кодирования, используемому в utf-8, зерезервировав максимум 6 бит. 16^126 степени представляется достаточно большим числом, больше, чем гугол (10^100, что, в свою очередь, больше, чем количество атомов в обозримой части Вселенной — 10^80). Целая часть — ещё 4 бита, всего полтора байта. Дробную часть, то есть остаток от вычитания мантиссы в степени из исходного числа, сбросим последовательно четырёхбитными фрагментами. Размер ключа выравниваем на байт. И не забываем всё инвертировать для отрицательных чисел. Код будет ниже.

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

Ниже приведён код (C++) для подобного кодирования чисел с плавающей запятой. Для целых, очевидно, его можно записать несколько проще, не используя арифметических функций вроде pow.

/*
* Store - писатель данных по квартетам
*/
template <size_t length, char chfill>
class Store
{
  char buffer[length];
  char* bufend = buffer;
  bool bupper = true;


public: // write
  void store( unsigned value )
  {
    if ( !(bupper = !bupper) ) *bufend = (value << 4) | (chfill & 0x0f);
      else { *bufend = (*bufend & 0xf0) | value; ++bufend; }
  }
  template <class ... Values>
  void store( unsigned value, Values ... items )
  {
    return store( value ), store( items... );
  }

public:
  auto size() const -> size_t { return bufend - buffer + (bupper ? 0 : 1); }
  auto data() const -> const void* { return buffer; }

};


template <size_t length, char chfill>
struct negative_flush: public Store<length, chfill>
{
  auto put_mantis( int xpower, int mantis ) -> negative_flush&
  {
    if ( xpower >= 0 ) this->store( 0x3 - ((xpower >> 4) & 0x3), 0xf - (xpower & 0x0f) );
      else this->store( 0x4 | (-xpower >> 4) & 0x03, (-xpower) & 0x0f );
    return put_nibble( mantis );
  }
  auto put_nibble( unsigned u ) -> negative_flush&
  {
    return this->store( 0xf - (u & 0xf) ), *this;
  }
  template <class ... Nibbles>
  auto put_nibble( unsigned u, Nibbles... n ) -> negative_flush&
  {
    return put_nibble( u ).put_nibble( n... );
  }
};


template <size_t length, char chfill>
struct positive_flush: public Store<length, chfill>
{
  auto put_mantis( int xpower, int mantis ) -> positive_flush&
  {
    if ( xpower >= 0 ) this->store( 0x8 | (mantis != 0 ? 0x4 : 0) | ((xpower >> 4) & 0x3), xpower & 0x0f );
      else this->store( 0x8 | (0x3 - ((-xpower >> 4) & 0x3)), (0xf - (-xpower) & 0x0f) );

    return this->store( mantis ), *this;
  }
  auto put_nibble( unsigned u ) -> positive_flush&
  {
    return this->store( u ), *this;
  }
  template <class ... Nibbles>
  auto put_nibble( unsigned u, Nibbles... n ) -> positive_flush&
  {
    return put_nibble( u ).put_nibble( n... );
  }
};


template <class Store, class Value>
static auto make_double_key( Store& flush, const Value& value ) -> const Store&
{
  auto divide = value;
  auto mantis = (int)value;
  auto xpower = (int)0;

  static_assert( std::is_floating_point<Value>::value,
    "make_double_key( store, value ) would be called for floating point values!" );

// убедиться в корректности вызова функции - только положительные
  assert( value >= 0.0 );

// отсеять 0.0
// выделить целую часть и степень
  if ( value >= 1.0 ) while ( divide >= 16.0 ) { mantis = (divide /= 16.0); ++xpower; }
    else
  if ( value != 0.0 ) while ( divide < 1.0 ) { mantis = (divide *= 16.0); --xpower; }
    else
  return flush.put_mantis( 0, 0 );

  flush.put_mantis( xpower, mantis );

  if ( mantis != 0 )
  {
    auto  dleast = fmod( value, mantis * pow( 16, xpower ) );
    auto  dpower = pow( 16, xpower - 1 );

    for ( ; dleast != 0.0; dpower /= 16.0 )
    {
      auto  ndigit = (int)(dleast / dpower);

      flush.put_nibble( ndigit );
      dleast -= ndigit * dpower;
    }
  }

  return flush;
}

***

Если вам интересна тема морфологического поиска, напишите об этом в комментариях — возможно, в следующих материалах мы рассмотрим ее подробнее и расскажем о решении сложных лингвистических задач в контексте разработки продуктов МойОфис. И конечно, оставляйте ваши вопросы, замечания и предложения — мы ценим любую обратную связь читателей!