[Unicode]   Common Locale Data Repository : Bug Tracking Home | Site Map | Search

CLDR Ticket #6838(closed: fixed)

Opened 5 years ago

Last modified 5 years ago

Need better way to match a string to a collection of regex's

Reported by: jali01 Owned by: jali01
Component: xxx-tools Data Locale:
Phase: Review: yoshito
Weeks: Data Xpath:


In cldr/util/RegexLookup.java we a need better-than-linear-time method of matching a string to multiple regex's in a set,
we could use some sort of search tree algrithm instead (store regex's in a tree). For example (cldr/util/RegexLookup.java line 156):

public T get(String source, Object context, Output<String[]> arguments, Output<Finder> matcherFound, List<String> failures)

The above method iterates over regex's and tries to match them with the input string one at a time, which is O(n),
whereas we could achieve O(log(n)) using a search tree.

Other examples:

line 196: public List<T> getAll(String source, Object context, List<Finder> matcherList, List<String> failures)

line 221: public Map<String, T> getUnmatchedPatterns(Set<String> matched, Map<String, T> outputUnmatched)


Change History

comment:1 Changed 5 years ago by jali01

  • Owner changed from jali01 to anybody
  • Status changed from new to assigned

comment:2 Changed 5 years ago by jali01

  • Owner changed from anybody to jali01

comment:3 Changed 5 years ago by emmons

  • Milestone changed from UNSCH to 25M1

comment:4 Changed 5 years ago by jali01

  • Review set to yoshito

comment:5 Changed 5 years ago by yoshito

  • Status changed from assigned to closed
  • Resolution set to fixed

comment:6 Changed 5 years ago by emmons

  • Milestone 25M1 deleted

Milestone 25M1 deleted


Add a comment

Modify Ticket

as closed
Next status will be 'new'
Next status will be 'closed'

E-mail address and user name can be saved in the Preferences.

Note: See TracTickets for help on using tickets.