DevChallenge 2020 Backend

Шаг 1-2. Запуск приложения и тестов

Чтобы запустить приложение и тесты, нужно выполнить команду:

docker-compose up

Данная команда, после установки, автоматически запускает команду,

npm start

которая в себя включает две команды.

npm run test
npm run prod

Таким образом, тесты и приложение запускаются одновременно.

Шаг 3. Описание API

API приложения, расположено в файле ./api.js.

API делится на два контроллера:

• Articles controller (./controllers/articles.js)
  • GET /articles
  • POST /articles
  • GET /articles/:id
• Duplicate groups controller (./controllers/duplicate_groups.js)
  • GET /duplicate_groups

GET /articles

Возвращает уникальные статьи без дубликатов в формате JSON-объекта, где:

{
  "articles": [
    {
      "id": "5f95c11ed2f6692d5c6112c4",
      "content": "It is an example text number one",
      "duplicate_article_ids": [
        "5f95c125d2f6692d5c6112c5",
        "5f95c13ed2f6692d5c6112c8"
      ]
    }
  ]
}

• articles -- массив уникальных статей
• id -- идентификатор статьи
• content -- содержание статьи
• duplicate_article_ids -- массив идентификаторов дубликатов

ВНИМАНИЕ! Так-как используется СУБД MongoDB, то идентификаторы не числовые, и имеют тип данных ObjectId.

POST /articles

Принимает данный запрос JSON-объект, где:

{
  "content": "It is an example text number one"
}

• content -- содержание статьи.

Возвращает сервер эту же статью с её идентификатором и дубликатами, в формате JSON-объекта, где:

{
  "id": "5f962beb7cd7eb1be8688d7f",
  "content": "It is an example text number four",
  "duplicate_article_ids": [
    "5f95c11ed2f6692d5c6112c4",
    "5f95c125d2f6692d5c6112c5",
    "5f95c13ed2f6692d5c6112c8"
  ]
}

• id -- идентификатор статьи
• content -- содержание статьи
• duplicate_article_ids -- массив идентификаторов дубликатов

GET /articles/:id

Пример. /articles/5f95c11ed2f6692d5c6112c4

Возвращает статью по её идентификатору с дубликатами в формате JSON-объекта, где:

{
  "id": "5f95c11ed2f6692d5c6112c4",
  "content": "It is an example text number one",
  "duplicate_article_ids": [
    "5f95c125d2f6692d5c6112c5",
    "5f95c13ed2f6692d5c6112c8",
    "5f962beb7cd7eb1be8688d7f"
  ]
}

• id -- идентификатор статьи
• content -- содержание статьи
• duplicate_article_ids -- массив идентификаторов дубликатов

GET /duplicate_groups

Возвращает все группы дубликатов в формате JSON-объекта, где:

{
  "duplicate_groups": [
    [
      "5f95c11ed2f6692d5c6112c4",
      "5f95c125d2f6692d5c6112c5",
      "5f95c13ed2f6692d5c6112c8",
      "5f962beb7cd7eb1be8688d7f"
    ]
  ]
}

• duplicate_groups -- двухмерный массив идентификаторов. Массив групп.
• Группа -- это массив идентификаторов дубликатов.

Шаг 4. Методология

Проект реализован на технологическом стеке MongoDB-Express-NodeJS (MEN).

Преимущество данного стека, в том что серверная и клиентская часть, пишется на одном языке программирования JavaScript.

В приложении есть своя реализация MVC, что позволяет удобно разделять код на разные логические структуры.

Преимущество Express в middleware'ах. Всё приложение, по сути, является цепочкой из промежуточных функций, которые можно легко добавлять и удалять. Это позволяет легко расширять приложение.

Модели в данном приложении, являются схемой коллекций в БД. Всего здесь одна модель Article, с которой работают контроллеры.

Контроллеры в данном приложении, являются набором функций, которые экспортируются и импортируются в каком-то из запросов, в качестве функции обработчика.

В контроллере Articles (./controllers/articles.js) в методах post, get и getById используется алгоритм компрессии текстов и их сравнения.

Данный алгоритм реализован в библиотеке bloom-text-compare.

Подключение библиотеки

const btc = require('bloom-text-compare');

Использование

const text1 = 'Example text number one';
const text2 = 'Example text number two';

const list1 = text1.split(' ');
const list2 = text2.split(' ');

const hash1 = btc.hash(list1);
const hash2 = btc.hash(list2);

const distance = btc.compare(hash1, hash2);

console.log(distance);

В данной библиотеке реализовано два метода: hash и compare.

Метод hash

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

Далее метод компрессирует текст и превращает его в массив из десяти 32-ух битных чисел. Это и есть хэш.

Метод compare

На вход, метод принимает два хэша, и возвращает число от 0 до 1. Это число, является процентом совпадений в тексте.

Для получения данного процента, нужно в цикле пройтись по двум хэшам, и посчитать все AND'ы и OR'ы. Для этого нужно просуммировать результаты побитовых И (&), и просуммировать результаты побитовых ИЛИ (|). Их отношение, и есть процент совпадений в тексте.

Преимущество данного алгоритма в том, что он очень быстро работает с большими объемами текста и дает довольно точный результат.

Шаг 5. Уточнение и следующие шаги по улучшению

Файл конфигураций находится в config/default.json

{
  "PORT": 8000,
  "MONGOURI": "mongodb://devchallenge-db:27017/devchallenge2020",
  "THRESHOLD": 0.7
}

В данном файле установленны 3 константы. Конкретно нас интересует константа THRESHOLD, которая устанавливает порог. Тут установлен порог в 70%, так-как при таком проценте, алгоритм работает более адекватно (И для маленьких, и для больших текстов). Но можно и увеличить порог, если работа будет вестись с очень большими текстами.

Также, в проекте не реализована нормализация слов. Поэтому слова "go", "goes" и "went" считаются разными.

Шаги по улучшению проекта

1. Добавить в алгоритм больше компрессии. Откидывать гласные буквы, так-как по большой части, для распознавания слова, достаточно и согласных. Удалять слова меньше 4 букв, так-как в зачастую, это слова приставки, артикли. С большой вероятностью, они будут повторяться, в двух текстах дубликатах.
2. Добавить нормализацию слов
3. Оптимизация циклов и запросов