Сравнение строк (Посимвольное, Dice coefficient)


#1

В elastic есть 2000 документов, которые содержат название бренда

Например:

  • Валио
  • Nesquick
  • Невские берега
  • Невские сыры
  • Невские

Задача:
    использовать elastic для нахождения бренда в передаваемой строке


Например:
   передаем в elastic строку >>> "Невские берега пирожные"
   должны получить из elastic ответ <<< "Невские берега"

Другие примеры:
    передаем >>> невские пирожные
    получаем <<< невские                            (важно: "невские" более релевантный результат, чем "невские берега". Тоесть, алгоритм должен учитывать, что необходимость перестановки букв (из "берега" в "пирожные") должно понижать score)

    передаем >>> пирожные берега невские
    получаем <<< невские           (порядок слов в строке важен)

    передаем >>> невс пирож
    получаем <<< невские           (тут видно, что совпадение лишь относительное. Тоесть, чтобы мы не передали, всегда должен возращаться какой то результат (близко к использованиею ngram) )

Я бы использовал ngram, но на запрос "Невские пирожные" -> более релевантным ответом будет "Невские берега", а не "Невские". Потому что в "Невские берега" больше совпадающих ngram.
Так же, ngram не учитывает порядок слов и запрос "салат берега невские" -> может считать "невские берега" релевантным ответом

Я бы хотел что то ближе к посимвольному сравнению.
На самом деле, я нашел, что Dice coefficient корректно выполняет мою задачу по сравнению строк ( https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Dice's_coefficient почти тот же ngram, но с понижением score за не совпадение ngram)

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

  1. Я иду по правильному пути, мне действительно стоит писать собственный скрипт сравнения строк?
  2. Скрипт стоит писать в query (script_score) или "Similarity module" ( https://www.elastic.co/guide/en/elasticsearch/reference/current/index-modules-similarity.html )

Спасибо!

Вот пример моих документов:

#!/bin/bash

HOST="localhost:9200"
INDEX="tmp2509"
TYPE="doc"


curl -X PUT "$HOST/$INDEX?pretty" -H 'Content-Type: application/json' -d'
{
   "settings":{

      "analysis":{
         "analyzer":{
            "my_analyzer":{
               "type":"custom",
               "tokenizer":"keyword"
            }
         }
      }

   },

  "mappings": {
    "'$TYPE'": {
      "properties": {
        "brandName": {
          "type": "text",
          "analyzer":"my_analyzer"
        }
      }
    }
  }
}
'

curl -XPOST "$HOST/$INDEX/_bulk?pretty" -H "Content-Type: application/x-ndjson" -d '
{ "index" : { "_index" : "'$INDEX'", "_type" : "'$TYPE'", "_id" : "1" } }
{ "brandName" : "невские берега" }
{ "index" : { "_index" : "'$INDEX'", "_type" : "'$TYPE'", "_id" : "2" } }
{ "brandName" : "невские бер" }
{ "index" : { "_index" : "'$INDEX'", "_type" : "'$TYPE'", "_id" : "3" } }
{ "brandName" : "невские" }
{ "index" : { "_index" : "'$INDEX'", "_type" : "'$TYPE'", "_id" : "4" } }
{ "brandName" : "невские сыры" }
{ "index" : { "_index" : "'$INDEX'", "_type" : "'$TYPE'", "_id" : "5" } }
{ "brandName" : "валио" }
{ "index" : { "_index" : "'$INDEX'", "_type" : "'$TYPE'", "_id" : "6" } }
{ "brandName" : "valio" }
{ "index" : { "_index" : "'$INDEX'", "_type" : "'$TYPE'", "_id" : "7" } }
{ "brandName" : "nesquick" }
'

curl -X GET "$HOST/$INDEX/$TYPE/_search?pretty" -H 'Content-Type: application/json' -d'
{
    "query": {
        "match" : {
            "brandName" : "невские пирожные"
        }
    }
}
'

echo "----------------------------------------------"
echo "Пример для ваших запросов:"
echo "curl -X GET \"$HOST/$INDEX/$TYPE/_search?pretty\" -H 'Content-Type: application/json' -d'
{
    \"query\": {
        \"match\" : {
            \"brandName\" : \"невские пирожные\"
        }
    }
}
'
"

(Igor Motov) #2

Если их только 2000, то может перевернуть задачку и искать бренды в передаваемой строке с помощью перколятора?


#3

Спасибо. Но это не решило задачу

При использование перколятора у меня получается:

передаю >>> "невские пирожные"
получаю <<<

  1. "невские сыры" (score 0.28)
  2. "невские берега" (score 0.28)
  3. "невские" (score 0.28)

Необходимо было получить "невские" с более высоким score

Вот код:

#!/bin/bash

HOST="159.69.92.47:9200"
INDEX="tmp2609_6"
TYPE="doc"

read -p "Press enter to: создание индекса"
curl -X PUT "$HOST/$INDEX?pretty" -H 'Content-Type: application/json' -d'
{
  "mappings": {
    "'$TYPE'": {
      "properties": {
        "brandName": {
          "type": "text"
        },
        "query": {
          "type": "percolator"
        }
      }
    }
  }
}
'

read -p "Press enter to: заполнение документов"
curl -XPOST "$HOST/$INDEX/_bulk?pretty" -H "Content-Type: application/x-ndjson" -d '
{ "index" : { "_index" : "'$INDEX'", "_type" : "'$TYPE'", "_id" : "1" } }
{ "query" : { "match" : { "brandName" : "невские берега" } } }
{ "index" : { "_index" : "'$INDEX'", "_type" : "'$TYPE'", "_id" : "2" } }
{ "query" : { "match" : { "brandName" : "невские бер" } } }
{ "index" : { "_index" : "'$INDEX'", "_type" : "'$TYPE'", "_id" : "3" } }
{ "query" : { "match" : { "brandName" : "невские" } } }
{ "index" : { "_index" : "'$INDEX'", "_type" : "'$TYPE'", "_id" : "4" } }
{ "query" : { "match" : { "brandName" : "невские сыры" } } }
{ "index" : { "_index" : "'$INDEX'", "_type" : "'$TYPE'", "_id" : "5" } }
{ "query" : { "match" : { "brandName" : "валио" } } }
{ "index" : { "_index" : "'$INDEX'", "_type" : "'$TYPE'", "_id" : "6" } }
{ "query" : { "match" : { "brandName" : "valio" } } }
{ "index" : { "_index" : "'$INDEX'", "_type" : "'$TYPE'", "_id" : "7" } }
{ "query" : { "match" : { "brandName" : "nesquick" } } }
'

read -p "Press enter to: произведение поиска"
curl -X GET "$HOST/$INDEX/_search?pretty" -H 'Content-Type: application/json' -d'
{
    "query": {
        "percolate" : {
            "field" : "query",
            "document" : {
                "brandName" : "невские пирожные"
            }
        }
    }
}
'

Пока буду изучать в сторону -> написания script_score
Но если появятся какие либо идеи, буду рад =)


#4

У меня получилось уместить это в скрипте:

curl -X GET "localhost:9200/index/doc/_search?pretty" -H 'Content-Type: application/json' -d'
{
    "size" : 3,
    "query": {
        "function_score": {
            "query": {
                "match_all": {}
            },
            "script_score" : {
                "script" : {
                  "lang": "painless",
                  "source": "String forSearch = params.my_modifier; String haveInBase = doc['"'brandName'"'].value; Set nx = new HashSet(); Set ny = new HashSet(); for (int i=0; i < forSearch.length() - 1; i++) { char x1 = forSearch.charAt(i); char x2 = forSearch.charAt(i+1); String tmp = \"\" + x1 + x2; nx.add(tmp); } for (int j=0; j < haveInBase.length()-1; j++) { char y1 = haveInBase.charAt(j); char y2 = haveInBase.charAt(j+1); String tmp = \"\" + y1 + y2; ny.add(tmp); } Set intersection = new HashSet(nx); intersection.retainAll(ny); double totcombigrams = intersection.size(); return (2*totcombigrams) / (nx.size()+ny.size())",
                  "params": {
                    "my_modifier": "Невские берега"
                  }
                }
            }
        }
    }
}
'

# То что выше, это однострочный:
String forSearch = params.my_modifier;
String haveInBase = doc['"'brandName'"'].value;

Set nx = new HashSet();
Set ny = new HashSet();

for (int i=0; i < forSearch.length() - 1; i++) {
    char x1 = forSearch.charAt(i);
    char x2 = forSearch.charAt(i+1);
    String tmp = "" + x1 + x2;
    nx.add(tmp);
}

for (int j=0; j < haveInBase.length()-1; j++) {
    char y1 = haveInBase.charAt(j);
    char y2 = haveInBase.charAt(j+1);
    String tmp = "" + y1 + y2;
    ny.add(tmp);
}

Set intersection = new HashSet(nx);
intersection.retainAll(ny);
double totcombigrams = intersection.size();

return (2*totcombigrams) / (nx.size()+ny.size());

Вот теперь думаю, смогу ли я поместить этот скрипт в "Similarity module", чтобы не слать весь скрипт при каждом запросе.
И будут ли у меня проблемы с производительностью.


(Igor Motov) #5

Я думаю, что это все можно упростить путем добавления веса к запросам чтобы короткие запросы имели больше веса, но пока нет времени с этим поиграться - попробую посмотреть чуть позже.

Скрипты можно хранить на сервере - https://www.elastic.co/guide/en/elasticsearch/reference/current/modules-scripting-using.html#modules-scripting-stored-scripts


#6

Спасибо за помощь )

Свою задачу я все же решил именно через script_score
Так или иначе, встроенные в elastic решения мне вряд ли помогут, потому что условия подсчета релевантности очень и очень специфичны

Просто для истории, мой результат получился такой:

curl -X GET "159.69.92.47:9200/wow2/doc/_search?pretty" -H 'Content-Type: application/json' -d'
{
    "query": {
        "function_score": {
            "query": {
                "match_all": {}
            },
            "script_score" : {
                "script" : {
                    "lang": "painless",
                    "source": "String rowForSearch = params.my_modifier; String brandInBase = doc['"'brandName'"'].value; float result = 0; String[] arrayForSearch = /\\ /.split(rowForSearch); String[] arrayBrandInBase = /\\ /.split(brandInBase); while (arrayForSearch.length != 0) { float r = 0;int successWord = 0;int successSequence = 0;int lenWord = arrayForSearch.length;for (int iWord = 0; iWord < lenWord; iWord++) { int successChar = 0; if (arrayBrandInBase.length <= successWord) { break; } char[] charsBrand = arrayBrandInBase[successWord].toCharArray(); char[] charsForSearch = arrayForSearch[iWord].toCharArray(); int lenChar = charsForSearch.length;for (int iChar = 0; iChar < lenChar; iChar++) { if (charsBrand.length <= iChar) { break; } if (charsForSearch[iChar] == charsBrand[iChar]) { ++successChar;continue; } break; } if (1 < successChar) { ++successWord; successSequence += successChar; } else { r = (float) successSequence; break; } } r = (float) successSequence; if (result < r) { result = r; } String[] wow = new String[arrayForSearch.length - 1]; System.arraycopy(arrayForSearch, 1, wow, 0, arrayForSearch.length - 1); arrayForSearch = wow; } return result - 0.1 * brandInBase.length();",
                    "params": {
                        "my_modifier": "невское пирожное"
                    }
                }
            }
        }
    }
}
'

// При этом документы имеют "tokenizer":"keyword"

// это однострочная версия этого кода: 

    String rowForSearch = "";
    String brandInBase = "";
    float result = 0;

    // - тримем все спецсимволы
    rowForSearch = rowForSearch.replaceAll("[\'\"\.]"," ");

    // - удаляем все слова менее 2 букв
    rowForSearch = rowForSearch.replaceAll("\\b\\w{1,2}\\b\\s?", "");

    String[] arrayForSearch = rowForSearch.split(" ");
    String[] arrayBrandInBase = brandInBase.split(" ");

    while (arrayForSearch.length != 0) {
        float r = 0;

        int successWord = 0;
        int successSequence = 0;

        // проходимся по словам
        int lenWord = arrayForSearch.length;
        for (int iWord = 0; iWord < lenWord; iWord++) {
            int successChar = 0;

            // проверяем доступность
            if (arrayBrandInBase.length <= successWord) {
                break;
            }

            // проходимся по буквам слова
            char[] charsBrand = arrayBrandInBase[successWord].toCharArray();
            char[] charsForSearch = arrayForSearch[iWord].toCharArray();
            int lenChar = charsForSearch.length;
            for (int iChar = 0; iChar < lenChar; iChar++) {
                // посимвольная сверка
                if (charsBrand.length <= iChar) {
                    break;
                }

                if (charsForSearch[iChar] == charsBrand[iChar]) {
                    ++successChar;
                    continue;
                }

                break;
            }

            // если у слова были совпадения
            if (1 < successChar) {
                // записываем результат по слову
                ++successWord;
                successSequence += successChar;
            } else {
                // если у слова не было совпадений
                // Возвращаем результат
                r = (float) successSequence;
                break;
            }
        }

        r = (float) successSequence;

        if (result < r) {
            result = r;
        }

        for (int i = arrayForSearch.length-1; i >= 0; i--) {
            arrayForSearch[i+1] = arrayForSearch[i];
        }
    }

    return result - 0.1 * brandInBase.length();

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


(system) #7

This topic was automatically closed 28 days after the last reply. New replies are no longer allowed.