Оцените задачу, которую я даю кандидатам на работу. Не слишком ли я суров?
Когда ко мне попадают програмисты на собеседование, то я мучаю их задачами из реальной жизни. И вот что-то задумался я - а не слишком ли я суров? Вот смотрите, есть такая задача:
Шиппинговая компания из Штатов имеет партнера в Англии. Эдакий английский локальный DHL. Эта английская компания ставит софт на компьютеры клиентов и те могут забить туда данные посылки. Затем они получат оплаченнную почтовую этикету. Конечный клиент (сиречь - отправитель) забивает адрес получателя в штатах, вес, размер посылки, свой адрес у него в настройках програмы, и еще клиент должен вбить описание товара. Софт отправляет XML пакет англичанам на сервер, те отправляют его нам в штаты и мы возвращаем или готовую этикетку или сообщение об ошибке. Проблема в том, что некоторым клиентам лень писать хорошее описание и они порой вбивают так вот от балды какие-то "ацуккаукцука цкуцукп у". Когда штатовская компания шлет такие данные в американскую таможню, то их штрафуют за явный бред и попытку переложить контроль над качеством данных на таможню. Задача: найти способ автоматически выявлять такие вот случайно забитые описания товаров с высокой вероятностью.
Детали:
1) нет, мы не можем следить за скоростью набора, так как мы не контролируем шиппинговую программу.
2) нас не волнует если человек написал "зеленый горошек" на посылке с настольной лампой. В таком случае таможня штрафует отправителя, так как он солгал. А вот за "куацук цукцук" штрафуют нас, так как таможеннник справедливо указывает на то, что мы должны были знать что в посылке нету "куацук цукцук" и должны были отредактировать описание до отправки в таможню.
3) не требуется идеального решения. Требуется вероятностное. То есть понятно что посадить человека мониторить все посылки можно, но дорого. Хочется иметь что-то вроде автосортировки, которая будет отсеивать 85% посылок как наверняка правильные (и пропускать без модерации), 10% как точно неправильные (и отбивать такие запросы отдавая сообщение об ошибке вместо лейбла), а на ручную модерацию отправлять только последние 5% сомнительных случаев.
Так вот в чем мой вопрос: а не слишком ли я жесток? Не слишком ли эта задача сложная? То есть подчеркну: я не прошу код у людей немедленно. Я прошу описание наметок, как можно решать задачу, что примерно будет код делать.
Сразу вдогонку: два самых популяррных предложения: 1) использовать словари и проверку орфографиии и 2) совать текст в гугль на предмет опознает ли он слово. Оба плохие, так как 1) рабочие склада обычно неграмотны и используют сокращения, 2) механика руки делает наборы случайных символов не случайными. К примеру ывпаывп гугль даже за опечатку не считает.
Использовать либу, в которой реализован какой-нибудь Нечеткий поиск. Или самим написать. Это задача довольно комплексная. Возможно свою БД, самописную. Проще какую-нибудь кафедру MIT подключить, чем искать мидла, который вам на коленке Oracle напишет. Одним Расстоянием Левенштейна может и не обойтись. habrahabr.ru/post/114997 algolist.manual.ru/search/fsearch
Нужно взять распределение букв/слогов в эталонном тексте и сравнить его с таким же распределением на этикетке. Если в пределах некоторой погрешности они совпадают то все ОК. Пропускаем этикетку дальше.
К сожалению нет. Дело в том, что средня длина описание товара всего пара-тройка слов. То есть частотное распределение букв тут не работает. Дисперсия слишком велика.
Это популярный ответ, но он плохой, так как механика руки делает наборы случайных символов не случайными. К примеру "ывпаывп" гугль даже за опечатку не считает.
Как раз подумал про "qwerty", когда писал ответ. Такие комбинации (подряд буквы на клавиатуре), но которые находятся поисковиком, нужно обрабатывать в-ручную с записью в базу подтверждённых или отвергнутых слов.
Белый и черный списки на основе пополняемых словарей.
Белый - слова и сокращения которые уже есть в вашей базе, плюс обычный словарь.
Черный - явно недопустимые вхождения комбинаций букв и стоп-слова.
Всё это можно дополнить каким-нибудь алгоритмом фильтрации по составу слова.
Вероятностная часть - анализировать процент вхождения в эти списки.
Очевидно, что нужен комплексный подход - использование нескольких методов и комбинирование их результатов.
На первом этапе проверка просто по словарю - есть ли такие слова, затем можно проверять есть ли существительное, есть ли прилагательное, в общем морфология, синтаксис и пунктуация.
Словарей должно быть два - один общий, а другой является базой всех отправлений через сервис (используемые сокращения и жаргон попадёт в него).
Логично будет договориться с другой крупной транспортной компанией и приобрести у них базу описаний отправлений.
На втором этапе статистический подход - распределение букв по клавиатуре, длина и количество слов, насколько слова похожи на слова (приставки, слоги, окончания). Здесь же можно посчитать количество информации (энтропию) описания и сравнить её со средним значением.
И на третьем этапе - помощь интернета, поиск описания на яндекс маркете, amazon, ebay и прочем.
Каждый этап выставляет свой балл и затем они комбинируются с коэффициентами в результирующий балл.
У решения на самом деле два уровня.
Первый это заценить таки (не) случайность вводимого набора. Мы смотрим только на строчку символов. Тут два основных варианта: или мы берем огромный существующий текст и используем его как донор хороших описаний для Байеса или, что по сути тоже самое, но другим математическим аппаратом, цепи Маркова используем. Грубо говоря в обоих случах мы используем тот факт, что в английском языке после буквы скажем E буквы R и U идут с разной вероятностью. И эта вероятность как раз и характеризует язык. Короткие строки, когда описание состоит всего из одного слова о 3х-4х буквах) режутся по словарю, так как статистические методы там не работают. Зато тут хоршо работает словарь в лоб. Если человек в слове car ошибку посадил, то один хрен нельзя понять что это.
Второй слой заключается как раз в том, что хотя набор данных поступает и в случайном порядке, но его природа изначально не случайна. Клиенты шиппинговой компании подчиняются тому же нормальному распределению как и все остальные. Ну или Правилу Парето, если кому эта терминология привычнеее. Совершенно случайный клент не в курсе еще какие поля важны, а какие нет. Он, как правило, вполне аккуратен. К тому же ему меньше смысла вбивать билиберду, так как его трудозатраты изменятся на пару секунд. Основной источник белиберды это постоянно отправляющий посылки ленивый работник какого-то склада интернет магазина или чего-то аналогичного. Он во-первых шлет не свое, а во-вторых для него как раз пара секунд на каждой посылке складываются в весомый выигрыш. У нас есть адрес отправителя всегда - ибо это посылка. То есть мы всегда в курсе кто шлет много и кто часто конит и, соответственно, кто работает честно. Это помогает нам сортировать сомнительный случаи когда наш Баес/Марков/частотное распределение дает нам 50 на 50.
Простой
