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

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

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

Привет, Хабр! Меня зовут Андрей Коваленко (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;
}

***

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