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

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


Привет, Хабр! Меня зовут Андрей Коваленко (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 бита, всего полтора байта. Дробную часть, то есть остаток от вычитания мантиссы в степени из исходного числа, сбросим последовательно четырёхбитными фрагментами. Размер ключа выравниваем на байт. И не забываем всё инвертировать для отрицательных чисел. Код будет ниже.

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

Значение

Представление

1

c0 10

7

c0 70

16

c1 10

255

c1 ff

256

c2 10

1048576 = 16^5

c5 10

16^5 + 1

c5 10 00 01

0.1

be 19 99 99 99 99 99 9a

0.03125 = 1/32

bd 80

Ниже приведён код (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;
}

***

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

Комментарии (8)


  1. konosuba_es
    21.09.2022 13:07
    +2

    Здравствуйте, Андрей! Спасибо за материал. Тема очень интересная. Где можно получить подобные знания - я имею в виду, на стыке лингвистики, морфологии и ИТ? Может быть университеты, кафедры посоветуете?


    1. Keva
      21.09.2022 14:25
      +4

      Добрый день.

      Есть такое развлечение - смотрите книги по запросу 'information retrieval', и почти все будут путными. Статьи, в том числе и, конечно же, на habr.

      Ну и общение с себе подобными :)

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


      1. konosuba_es
        22.09.2022 11:11
        +2

        Благодарю.


  1. Zenitchik
    21.09.2022 18:59
    +1

    Обычный тип с плавающей точкой IEEE-754 содержит последовательно: бит знака, экспоненту в смещённом коде, остаток мантиссы или денормализованную мантиссу.

    Так вот, если откусить бит знака, а остальную часть интерпретировать как целое, то окажется, что сравнение этого числа соответствует сравнению модуля исходного числа.

    Откусываем бит знака, получаем целое число. Если бит знака - флаг, меняем знак на минус. В результате получается целое, отсортированное в том же порядке, как исходный float.


    1. Keva
      21.09.2022 19:14
      +4

      Да, конечно.

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

      Физическое представление такого оглавления - разного рода деревья, например, префиксное или patricia. Ключ - последовательность байт. Поиск по диапазону - поиск первого GE ключа для нижней границы и последовательная выборка ключей, пока LE верхней границе.

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


      1. Zenitchik
        22.09.2022 17:35

        Я имел в виду, что задачу представления float можно свести к задаче представления int, которая, как Вы сами пишете

        несколько проще, не используя арифметических функций вроде pow.


        1. Keva
          22.09.2022 19:02
          +1

          Ну да, вместо pow() можно делать в коде битовые сдвиги на 4, поскольку база 16.


    1. code_panik
      22.09.2022 19:01
      +2

      Вплоть до последних версий стандарта представление таких чисел implementation-defined, https://eel.is/c++draft/basic.fundamental#12. Значит, реализация может различаться уже на уровне разных версий компиляторов.