매칭 알고리즘

개요

매칭 알고리즘은 이용자의 정보를 분석해 저장한 후, 저장된 정보의 활동으로 수집된 추가정보를 학습시켜 보다 빠르고 효과적인 정보 간 매칭 시스템을 제공한다. 현재 플랫폼 사업에서 쉽게 볼 수 있다.

종류

아호 코라식 알고리즘

아호 코라식 알고리즘(Aho-Coraisck string matching algorithm)은 범용적인 일대다 패턴 매칭 알고리즘이다. KMP 알고리즘은 문자열 패턴 매칭에서 하나의 패턴이 하나의 문자열에 매핑이 되는지 선형시간에 판별한다. KMP 알고리즘과 비교해 아호 코라식 알고리즘은 좋은 시간복잡도를 보여준다.

• 만약, “cporogramming”이라는 문자열 내에서 “ogram”이라는 패턴은 KMP 알고리즘을 사용해 검색하면 선형시간 내에 검색할 수 있다. 그러나 여러 문자열 집합{“ogram”, “pro”, “mming”, “awwer”}을 검색하게 되면 “ogram”이란 패턴 하나를 검색했을 때보다 집합의 개수만큼 시간이 더 걸리게 된다. 시간복잡도는 을 가지게 되며 이는 패턴의 수가 많아질수록 비효율적이다. (m: 모든 패턴의 길이 합, z: 패턴 수, n: text 크기)
• 아호 코라식은 KMP의 시간복잡도 문제를 해결한다. 이는 여러 문자열 집합으로 검색해도 선형 시간 안에 끝낼 수 있다. 시간복잡도는 로 KMP의 시간복잡도 보다 개선된 형태이다. 아호 코라식은 수많은 검색엔진, 데이터마이닝 툴에서 채택하고 있는 패턴매칭 알고리즘이다. (m: 모든 패턴의 길이 합, n: text의 크기, k: 문자열 내에서 패턴의 발생 빈도)

게일-섀플리 알고리즘

게일-섀플리 알고리즘(Gale-Shapley Algorithm)은 서로에 대해 선호를 가진 지단 간 안정적 매칭을 찾아내는 알고리즘이다. 안정적 매칭은 두 집단에 속하는 사람들이 빠짐없이 모두 매칭에 성공하였으며, 매칭된 결과에 모든 사람이 만족하고 있는 상태를 말한다. 수학자인 로이드 섀플리 교수(Lloyd Shapley)가 동료 수학자 데이비드 게일(David Gale)과 함께 1962년 발표한 논문 《College Admissions and the Stability of Marriage》에 처음 등장하였다. 이들은 이 알고리즘을 발견하고, 현실에 적용해 효율적인 집단 간 매칭에 큰 기여를 한 공로로 2012년 노벨경제학상을 하버드 대학교 교수 앨빈 로스(Roth A.E.)와 공동 수상했다. 앨빈 로스는 병원과 레지던트 간의 매칭이나 2003년 뉴욕 공립학교 배정 문제 등에 이 알고리즘을 적용·발전시켰다.

사례

매칭 알고리즘은 많은 분야에서 시장 내 서비스 경쟁력을 강화하기 위해 사용하고 있다. 또한 지속적인 연구와 업데이트를 하고 있다.

액티비전

액티비전은 미국의 게임 개발회사로 2008년 비벤디 게임즈와 합병해 액티비전-블리자드로 출범했다. 이들은 2015년에 특허출원한 ‘멀티플레이 비디오게임에서의 소액결제 시스템과 그 방법(System and method for driving microtransaction in multiplayer video games)’이 특허등록을 허용받았다. 이 시스템의 알고리즘은 아래와 같다. 이 시스템은 매칭 과정에 소액결제 엔진을 추가해 유저들의 성향을 분석하고 소액 결제를 통해 구매한 아이템을 더욱 효과적인 세션에 매칭시켜주는 것이다.

센디

센디(SENDY)는 이사 매칭 플랫폼 ‘이사모아’의 벤티츠가 출시한 화물운송 매칭 플랫폼이다. 현재 비정기 화물 물류 시장은 29조 원에 달하는 규모를 보여주고 있다. 이 시장은 낮은 빈도로 용달 화물을 부르는 수요자와 언제 어디서 일을 수주 받게 될지 모르는 공급자 간 수급 불균형이 보이고 있다. 벤티츠는 이런 문제점을 해결하기 위해 3년간 약 10만 건의 이사 매칭을 통해 알고리즘을 개선해 수요분산, 공급자 매칭 알고리즘을 통한 합리적 비용으로 서비스를 제공하고자 한다. 센디는 용달 이사, 원룸이사 등 화물 운송 토탈 매칭 플랫폼으로 서비스를 확장해나갈 예정이다.

틴더

틴더(Tinder)는 전 세계 196여 개국에서 사용하는 글로벌 데이팅 앱이다. 틴더는 자사가 개발한 매칭 알고리즘을 사용하며 사용자에 대해 보다 세심하게 이해해 원하는 상대와의 매칭확률을 높이고, 매칭된 사람들과 의미 있는 관계로 나아갈 수 있도록 알고리즘을 설계했다.

집닥

㈜집닥은 인테리어 비교 견적 중개 플랫폼을 운영하는 인테리어 전문 기업이다. 집닥의 이들은 인테리어 시공을 원하는 고객이 가장 최적화된 인테리어 업체를 통해 공사를 진행할 수 있도록 기업부설 연구소에서는 매칭 시스템 알고리즘을 개발해 인테리어 O2O 시장 내 서비스 경쟁력을 지속해서 강화하고 있다.

매팅튜터

매팅튜터는 서울대 재학생 및 졸업생으로 구성된 교육 전문 스타트업 ‘리버옥션’이 출시한 과외중개 애플리케이션이다. 리버옥션은 매칭 알고리즘을 개발해 매팅튜터에 적용하였다. 매팅튜터의 매칭 알고리즘은 선생님과 학생 간의 거리, 학업 수준, 과외비 등을 종합 분석해 학생에게 적합한 선생님을 위주로 정리해 보여주는 서비스이다. 학생마다 다른 학업 상황을 알고리즘으로 분석해 과외 선생님을 구하는 데 소비하는 시간을 절약하며 개인정보 노출을 최소화한다.