매칭 알고리즘

매칭 알고리즘(Matching Algorithm)

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

종류

아호 코라식 알고리즘

아호 코라식 알고리즘(Aho-Corasick 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년 뉴욕 공립학교 배정 문제 등에 이 알고리즘을 적용·발전시켰다.

사례

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

매칭튜터

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

㈜집닥

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

틴더

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

센디

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

액티비전

액티비전 매칭 시스템 알고리즘 특허

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

참고 자료

• 두산백과, 〈게일-섀플리 알고리즘〉, 《네이버 지식백과》
• vyujing, 〈아호 코라식 알고리즘(Aho–Corasick string matching algorithm)〉, 《티스토리 》, 2015-09-28
• Scott Carey, 〈데이팅 앱 '틴더'의 매칭 개선 비결, 'AWS 이미지 인식 기술'〉, 《ciokorea》, 2018-12-10
• 전화성 씨엔티테크 대표이사, 〈(전화성의 기술창업 Targeting)41. 인테리어 O2O 서비스의 인공지능 융합〉, 《전자신문》, 2018-10-28
• 한경닷컴 뉴스팀, 〈매칭 알고리즘을 활용한 맞춤형 과외중개 앱, ‘매칭튜터’ 출시〉, 《한국경제》, 2017-03-17
• 김재희 IT 칼럼니스트, 〈화물운송 매칭플랫폼 “수급불균형, 알고리즘으로 해결"〉, 《VENTURE SQUARE》, 2018-01-15
• 전투펭귄, 〈액티비전, 매칭시스템 특허〉, 《네이버 블로그》, 2017-10-19

같이 보기

• 알고리즘

이 매칭 알고리즘 문서는 알고리즘에 관한 글로서 검토가 필요합니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 문서 내용을 검토·수정해 주세요.

블록체인 : 블록체인 기술, 합의 알고리즘, 암호 알고리즘, 알고리즘 □■⊕, 블록체인 플랫폼, 블록체인 솔루션, 블록체인 서비스 채굴 알고리즘 SHA-256 • X11 • X11고스트 • X13 • X14 • X15 • X16R • X17 • 그로스톨 • 네오스크립트 • 니스트5 • 리라2알이 • 미리아드-그로스톨 • 블레이크 • 블레이크2 • 블레이크B • 블레이크2B • 블레이크256R8 • 블레이크256R14 • 스컹크해시 • 스케인 • 스크립트 알고리즘 • 스크립트엔 • 엘비알와이(LBRY) • 이더해시 • 이퀴해시 • 제반 • 쿼크 알고리즘 • 큐빗 알고리즘 • 크립토나이트 • 크립토나이트 라이트 • 타임트래블10 • 텐서리티 • 파스칼 • 프로그작업증명(ProgPoW) 매칭 알고리즘 BM25 • FAISS • 경매 • 더치 경매 • 매칭 알고리즘 • 매칭튜터 • 벡터검색 • 비크리 경매 • 센디 • 집닥 • 튜다 • 틴더 추천 알고리즘 TF-IDF • 역문서빈도(IDF) • 용어빈도(TF) • 추천 알고리즘 • 콘텐츠 기반 필터링 • 협업 필터링 고급 검색 알고리즘 AND-OR 검색 트리 • 국소 검색 알고리즘 • 국소 다발 검색 • 모의정련 • 언덕 오르기 검색 • 유전 알고리즘 대항 검색 검색의 차단 • 알파베타 가지치기 • 전방 가지치기 • 최소최대 알고리즘 제약 만족 문제 국소검색 • 역추적검색 • 제약전파 게임이론 게임이론 • 공유지의 비극 • 내시균형 • 메커니즘 디자인 • 비협조게임 • 사회선택이론 • 역게임이론 • 제로섬게임 • 조정게임 • 죄수의 딜레마 • 치킨게임 • 팃포탯 • 협조게임 위키 : 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반