Отображение произвольных строк в значения RGB

Question

У меня есть огромный набор произвольных строк на естественном языке. Чтобы мой инструмент их проанализировал, мне нужно преобразовать каждую строку в уникальное значение цвета (RGB или другое). Мне нужен цветовой контраст, чтобы зависеть от сходства строк (чем больше строка отличается от других, тем больше должны быть их соответствующие цвета). Было бы идеально, если бы я всегда получал одно и то же значение цвета для одной и той же строки.

Любой совет, как подойти к этой проблеме?

Обновление расстояния между строками

Мне, вероятно, нужно «сходство», определяемое как расстояние, подобное Левенштейну. Разбор естественного языка не требуется.

То есть:

"I am going to the store" and 
"We are going to the store"

Аналогично.

"I am going to the store" and 
"I am going to the store today"

Аналогично (но немного меньше).

"I am going to the store" and 
"J bn hpjoh up uif tupsf"

Совсем не похоже.

(Спасибо, Welbog !)

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

Обновление по упрощению задач

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

Answer 1

Вам нужно больше проработать, что вы подразумеваете под "похожими строками", чтобы придумать подходящую функцию преобразования. Струны

 "I am going to the store" and 
"We are going to the store" 

считается похожим? Как насчет струн

 "I am going to the store" and 
"J bn hpjoh up uif tupsf" 

(все буквы в оригинале +1) или

 "I am going to the store" and 
"I am going to the store today"

? Исходя из того, что вы подразумеваете под «похожим», вы можете рассмотреть различные функции.

Если разница может основываться исключительно на значениях символов (в Юникоде или в любом другом месте), тогда вы можете попытаться суммировать значения и использовать результат в качестве оттенка для пространства HSV. Если длинная строка приводит к тому, что цвета становятся более разными, вы можете рассмотреть взвешивание символов по их положению в строке.

Если разница более сложная, например, из-за появления определенных букв или слов, вам необходимо это определить. Возможно, вы можете выбрать значения красного, зеленого и синего цветов в зависимости от количества Es, Ss и Rs в строке, если их много в вашем домене. Или выберите оттенок на основе отношения гласных к согласным или слов к слогам.

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

Answer 2

Звучит так, будто вы хотите какой-то хэш. Это не обязательно должно быть безопасно (так что ничего сложнее, чем MD5 или SHA), но что-то вроде:

char1 + char2 + char3 + ... + charN % MAX_COLOUR_VALUE

будет работать как простой первый шаг. Вы могли бы также сделать более причудливые вещи в соответствии с тем, чтобы каждый символ действовал как «амплитуда» для R, G и B (e может быть + 1R, + 2G и -4B и т. Д.), А затем просто складывать все значения строка ... зажмите их в конце, и у вас есть метод превращения строк произвольной длины в цвета как «цветовой хэш».

Answer 3

Вы можете использовать что-то вроде MinHash или какой-либо другой метод LSH и определять сходство как пересечение между наборами черепицы , измеренной коэффициентом Жакара . Хорошее описание есть в Mining of Massive массивов данных, Ch.3 Раджарамана и Уллмана.

Answer 4

Вот мое предложение (я думаю, что для этого алгоритма есть общее название, но я слишком устал его помнить):

Вы хотите преобразовать каждую строку в трехмерный точечный узел (r, g, b) (вы можете масштабировать значения так, чтобы они соответствовали вашему диапазону), чтобы следующая ошибка была минимизирована:

Error = \sum_i{\sum_j{(dist(node_i, node_j) - dist(str_i, str_j))^2}}

Вы можете сделать это:

1. Сначала присвойте каждой строке случайный цвет (r, g, b)
2. Повторяйте до тех пор, пока не сочтете нужным (например, ошибка корректируется меньше, чем \ epsilon = 0.0001):
   1. Выберите случайный узел
   2. Отрегулируйте его положение (r, g, b) так, чтобы ошибка была минимизирована
3. Масштабировать систему координат так, чтобы координаты каждого узла находились в диапазоне [0., 1.) или [0, 256]

Answer 5

Насколько важно, чтобы у вас никогда не было двух разных строк одинакового цвета?

Если это не так важно, может, это сработает?

Вы можете выбрать одномерное цветовое пространство, которое является "гомотопным" для круга: допустим, цветовая функция c(x) определена для x между 0 и 1. Тогда вам захочется c(0) == c(1).

Теперь вы берете сумму всех значений символов по модулю некоторого коэффициента масштабирования и переносите его обратно в цветовое пространство:

c( (SumOfCharValues(word) modulo ScalingFactor) / ScalingFactor )

Это может работать даже лучше, если вы определили «обёртывание» цветового пространства более высоких измерений и для каждого измерения выберите различную функцию SumOfCharValues; кто-то предложил чередовать сумму и длину.

Просто мысль ... HTH

Answer 6

Во-первых, вам нужно выбрать способ измерения сходства строк. Минимальное расстояние редактирования является традиционным, но его недостаточно для правильного упорядочивания строк, что вам понадобится, если вы хотите каждый раз назначать одни и те же цвета одним и тем же строкам - возможно, вы могли бы взвесить редактирование стоит по буквенной дистанции. Также минимальное расстояние редактирования само по себе может быть не очень полезным, если вы ищете сходство в речи, а не в письменной форме (если это так, сначала рассмотрите проход стволов / звукового потока) или какое-то другое чувство «сходства».

Затем вам нужно выбрать способ обхода видимого цветового пространства на основе этой метрики. Может быть полезным рассмотреть возможность использования HSL или HSV цветового представления - тогда алгоритм может стать таким же простым, как выбор начального оттенка и обход отсортированного корпуса, присвоение текущего оттенка каждой строке перед смещением ее на строку отличие от предыдущего.

Answer 7

Извините, но вы не можете делать то, что вы ищете, на расстоянии Левенштейна или чем-то подобном. RGB и HSV - это трехмерные геометрические пространства, но расстояние Левенштейна описывает метрическое пространство - гораздо более слабый набор противоречий без фиксированного числа измерений. Невозможно отобразить метрическое пространство в фиксированное число измерений, сохраняя при этом локальность.

Что касается аппроксимаций, однако, для единичных терминов вы можете использовать модификацию алгоритма, такого как soundex или metaphone, чтобы выбрать цвет; для нескольких терминов вы можете, например, применить soundex или метафон к каждому слову в отдельности, а затем суммировать их (с переполнением).

Answer 8

Возможно, я бы определил некоторую дельту между двумя строками. Я не знаю, что вы определяете как разницу (или «неравенство») двух строк, но наиболее очевидной вещью, о которой я мог подумать, была бы длина строки и количество вхождений определенных букв (и их индекс в строке) , Не должно быть сложно реализовать его таким образом, чтобы он возвращал один и тот же код цвета в равных строках (если вы сначала делаете равное и возвращаетесь перед дальнейшим сравнением).

Когда дело доходит до фактического значения RGB, я бы попытался преобразовать строковые данные в 4 байта (RGBA) или 3 байта, если вы используете только RGB. Я не знаю, подойдет ли каждая строка в них (это может быть связано с конкретным языком?).