The efficient generation of high-fidelity entangled states is the key element for long-distance quantum communication, quantum computation, and other quantum technologies, and at the same time the most resource-consuming part in many schemes. We present a class of entanglement-assisted entanglement purification protocols that can generate high-fidelity entanglement from noisy, finite-size ensembles with improved yield and fidelity as compared to previous approaches. The scheme utilizes high-dimensional auxiliary entanglement to perform entangling nonlocal measurements and determine the number and positions of errors in an ensemble in a controlled and efficient way, without disturbing the entanglement of good pairs. Our protocols can deal with arbitrary errors, but are best suited for few errors, and work particularly well for decay noise. Our methods are applicable to moderately sized ensembles, as will be important for near term quantum devices.