Два года назад я выполнял задачу по сортировке строк в алфавитном порядке , учитывая каждый символ этой строки. В принципе это была задача скорее сортировки слов, чем строк в виде предложений, но большого отличия в этом нет. Конечно, в Java существуют встроенные инструменты для этих действий, но здесь надо было проверить мои способности в решении обычных логических задач (умения на основе своих решений составить определенный алгоритм).
Решать эту задачу обычным способом желания не было. Поэтому решил пойти привычным путём , когда делаешь так, как , возможно, делать не стоит, и никто так не делает, но сделать очень хочется. Так как в процессе изобретения велосипеда я не одинок, то решил лишний раз подтвердить свою принадлежность к данному комьюнити. Я решил попробовать реализовать внезапно возникшую идею представления строки в виде числа, то бишь сигнатуры. Причем надо было реализовать эту идею таким образом, чтобы число зависело от символов и их порядка, находящихся в строке. Т.е. сделать так, чтобы сортировка этих чисел была эквивалентна сортировке строк в алфавитном порядке по всем символам этих строк.
Решение
Что такое строка? В принципе это последовательность символов (обычно из таблицы ASCII кодов), - массив типа char[], где каждому элементу массива соответствует определенная буква самой строки.
Что такое тип char ? В Java это тип данных, занимающий 2 байта, где старший байт является просто кодировкой страницы UTF-8 (алфавита страны), а младший байт — кодировкой самого символа (буквы) из таблицы ASCII-кодов.
Что из этого возможно получить в виде выгоды? Ну, конечно же возможно! Вообще, старший байт , если мы сортируем список строк (слов) , описываемых одной страницей UTF-8 ASCII кодов, можно отбросить. Он является лишь маркером для выяснения страны происхождения данных строк. Значит одно из условий, для решения задачи данным способом — это необходимость того, что все строки происходят из одной страницы ASCII кодов.
Теперь осталось определить правилo для вычисления сигнатуры строки , чтобы ее значение зависело от последовательности символов в алфавитном порядке.
- Правило. Пусть мы имеем строку STR1, где каждый символ имеет определенный вес WEIGHT, что минимально возможное значение веса символа в любом месте строки , всегда больше значения суммы всех максимальных возможных последующих весов символов в этой строке.
Length — длина строки.
weight[i] — вес символа в строке, где i = 1 and i <= length (i — это номер символа в строке.)
Определяем такое правило :
weight [i] > sum (weight[i+1] … weight[length])
сигнатура строки STR1:
, где n — натуральное число, функция f(x) — вычисляет вес символа в строке являя собой вес weight(n), а результат sign<?> является суммой значений f(x).
Не уверен, что мои объяснения прояснили алгоритм решения этой задачи, но я хотя бы попробовал сделать это.
Я реализовал это решение на Java, создав довольно примитивное приложение. Код класса реализации представлен ниже. И этого, как ни странно, вполне достаточно для вычисления данной сигнатуры.
Код реализации данного функционала на Java представлен ниже.
Здесь метод getHashString вычисляет данную сигнатуру. В принципе ничего из ряда вон выходящего здесь нет. Но результат все-таки есть, и положительный.
Ниже представлен тестовый экран с результатом создания сигнатур очень неудобных строк для сравнения их по этим самым сигнатурам.
Строки в таблице представлены уже отсортированными по значениям сигнатур , видимых в столбце hash.
Попробуем добавить еще одну неудобную строку.
Как мы можем увидеть, добавилась строка с id = 57. Вообще она очень похожа со строкой с id=53. Ее длина больше, чем у 53-й строки, символы, находящиеся в ней категорически не отличаются от 53-й, кроме второго , который минимально меньше второго символа 53-й строки. y<z минимально. Но все равно сигнатура этой строки меньше, чем 53-й и сортировка, используя сигнатуры строк в алфавитном порядке, прошла успешно.
Вообще говоря, значение сигнатуры не является единственным и неповторимым. Оно зависит от основы, на которой вычисляется его значение. Меняя основу, можно получать ряды сигнатур, которые между собой соотносятся одинаково, и количество этих рядов в принципе может быть бесконечным.
Возникает вопрос : «А зачем все это нужно?» Дать на него категорический положительный ответ не могу. Возможны некоторые ситуации, при которых это целесообразно применять. К примеру, хранение в памяти словарей в виде бинарных деревьев, значительно убыстряющих поиск и добавление искомых слов и возможность отправки, вместо к примеру секретных слов, сигнатур, которые легко можно достать из хорошо защищенных структур данных…. Но это не точно.
Во всяком случае, задача была решена как мне хотелось : так , как не делают обычно, и как делать не стоит. Но оно же работает!