Минимальные сопоставления являются результатом продвинутой техники семантического сопоставления , техники, используемой в информатике для идентификации информации, которая семантически связана. [1]
Семантическое сопоставление было предложено в качестве действительного решения проблемы семантической неоднородности, а именно поддержки разнообразия в знаниях. [2] Для любых двух графоподобных структур, например, классификации, базы данных или XML-схем и онтологий , сопоставление - это оператор, который идентифицирует те узлы в двух структурах, которые семантически соответствуют друг другу. Например, применительно к файловым системам он может определить, что папка с меткой «автомобиль» семантически эквивалентна другой папке «автомобиль», поскольку они являются синонимами на английском языке.
Предлагаемый метод работает с легковесными онтологиями, а именно с древовидными структурами, где каждый узел помечен предложением на естественном языке, например, на английском языке. [3] Эти предложения переведены в формальную логическую формулу (на однозначном искусственном языке ). Формула кодирует значение узла с учетом его положения на графике. Например, если папка «автомобиль» находится в другой папке «красный», мы можем сказать, что в данном случае значение папки «автомобиль» - «красный автомобиль». Это переводится в логическую формулу «красный И автомобиль».
Результатом сопоставления является отображение, а именно набор семантических соответствий между двумя графами. Каждый элемент отображения связан семантическим отношением , например эквивалентностью . Среди всех возможных отображений минимальное отображение таково, что все другие элементы отображения могут быть вычислены из минимального набора за время, пропорциональное размеру входных графов (линейное время), и ни один из элементов минимального набора не может быть вычислен. упал, не препятствуя такому вычислению.
Основное преимущество минимальных отображений состоит в том, что они минимизируют количество узлов для последующей обработки. Обратите внимание, что это довольно важная функция, потому что количество возможных отображений может достигать n × m с размером n и m двух входных онтологий. В частности, минимальные отображения становятся критически важными для больших онтологий, например DMOZ , где даже относительно небольшие (неминимальные) подмножества числа возможных элементов отображения, потенциально миллионы из них, неуправляемы.
Минимальные сопоставления обеспечивают удобство использования. Многие системы и соответствующие интерфейсы, в основном графические, были предоставлены для управления сопоставлениями, но все они плохо масштабируются с количеством узлов. Визуализация больших графиков довольно беспорядочная. [4] Обслуживание небольших сопоставлений намного проще, быстрее и менее подвержено ошибкам.