Практика «Антиплагиат»

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

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

Оказывается расстояние Левенштейна можно использовать для того, чтобы сравнивать листинги программ (или вообще любые документы) друг с другом и находить самые похожие пары. Этим вам и предстоит заняться в данной задаче.

Скачайте проект Antiplagiarism.

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

Мы хотим, чтобы разница в пробелах, пустых строках или небольшом переименовании переменных не сбивала наш алгоритм. Поэтому вам нужно реализовать модифицированный алгоритм Левенштейна:

Он должен анализировать не последовательности символов, а последовательности токенов — лексических единиц. Например, в коде force = mass * acceleration 5 токенов: force, =, mass, *, acceleration. Код разбиения на токены уже реализован и на вход вашему алгоритму поступает список токенов. Один документ представляется типом DocumentTokens (который объявлен, как синоним List<string>).
Если два токена различаются, то будем учитывать ещё степень различия. Стоимость замены одного токена на другой в алгоритме Левенштейна будем вычислять с помощью формулы коэффициента Жаккара. Она тоже реализована за вас в методе GetTokenDistance класса TokenDistanceCalculator. Стоимость удаления/добавления токена равна единице, как и в оригинальном алгоритме.

Корректность работы проверяйте с помощью имеющихся в проекте модульных тестов.

using System;
using System.Configuration;
using System.Collections.Generic;
using System.Web.WebSockets;

// Каждый документ — это список токенов. То есть List&lt;string>.
// Вместо этого будем использовать псевдоним DocumentTokens.
// Это поможет избежать сложных конструкций:
// вместо List&lt;List&lt;string>> будет List&lt;DocumentTokens>
using DocumentTokens = System.Collections.Generic.List&lt;string>;

namespace Antiplagiarism
{

using System;

using System.Configuration;

using System.Collections.Generic;

using System.Web.WebSockets;

// Каждый документ — это список токенов. То есть List<string>.

// Вместо этого будем использовать псевдоним DocumentTokens.

// Это поможет избежать сложных конструкций:

// вместо List<List<string>> будет List<DocumentTokens>

using DocumentTokens = System.Collections.Generic.List<string>;

namespace Antiplagiarism

{

Стоимость решения этой задачи всего 100 рублей, купи решения у меня 🙂

Решения задачи с Ulearn

Практика «Антиплагиат»

Добавить комментарий Отменить ответ